Find the intersection of two strings in which characters appearing in both strings are returned (same sequence order as 1st String)

Question

I am using HashMap() for the problem but am facing issues with regards to order and occurrence of characters in output.

I tried to reverse the String builder both while iteration and after StringBuilder was created, still face another issues.

int l1 = inputStr1.length();
int l2 = inputStr2.length();

StringBuilder mkr = new StringBuilder();

HashMap<Character, Integer> res  = new HashMap<>();

for (int i = 0; i < l1; i++) {
           res.put(inputStr1.charAt(i),i);
        } 

    for (int j = 0; j < l2; j++) {
        if (res.containsKey(inputStr2.charAt(j))){
            mkr.append(inputStr2.charAt(j));

        }
}

mkr = mkr.reverse(); // Code only used in Test Scenario - 2
String result = mkr.toString();

if(result == null){return null;}

return result;

Test Scenario 1 - Input String 1 : Hello Input String 2 : world Expected output is: lo Actual output generated by my code: ol

Test Scenario 2 - [After reversing the StringBuilder] Input String 1: hi you are good Input String 2 : hi man Expected output is: hi a Actual output generated by my code: a ih

https://stackoverflow.com/questions/30662384/accept-2-strings-and-display-common-chars-in-them — Ravindra Ranwala, Aug 24 '19 at 16:12

score 0 · Answer 1 · answered Aug 24 '19 at 16:22

0

Your approach seems to be correct. But since you are expecting the final intersection characters to be in order with input String 1, instead of creating a hashmap of characters for string 1, and iterating over string 2, if those operations are reversed, it would give you the expected answer. But this may return duplicates. For e.g, if inputString1 = 'apple' and inputString2 = 'pot', this method may return two p's instead of 1. To avoid this problem, you can remove the character from hashmap once it matches with character in inputString1.

int l1 = inputStr1.length();
int l2 = inputStr2.length();

StringBuilder mkr = new StringBuilder();

HashMap<Character, Integer> res  = new HashMap<>();

for (int i = 0; i < l2; i++) {
       res.put(inputStr2.charAt(i),i);
} 

for (int j = 0; j < l1; j++) {
    if (res.containsKey(inputStr1.charAt(j))){
        res.remove(inputStr1.charAt(j));
        mkr.append(inputStr1.charAt(j);

    }
}

String result = mkr.toString();
if(result == null){return null;}
return result;

answered Aug 24 '19 at 16:22

Venkata Rathnam

348
1
5

Thank you for your comment. As per the testcases provided, repitition is fine. The Output should only contain - > No. of Character occurrences present on String 2 in the order of String1. Example Test Case : I tried running the code by creating a HashMap on String2 and iterated over String1 but found the below issue. Input string1 : Hello Input String 2 : world Expected output is: lo Actual output generated by my new code: llo – Bikash Bhagat Aug 25 '19 at 16:10
Thank you for the valuable comment. As per the problem statement, repetition is fine. The Output should only contain - > No. of Character occurrences present on String 2 in the order of String1. Example Test Case with remove() enabled on HashMap : Input 1: mmm Input 2 : mmm Expected output is: mmm Actual output: m Found below result, after running code by creating a HashMap on String2 and iterated over String1 without remove(): Input String1 : Hello Input String 2 : world Expected output is: lo Actual output: llo Could you please advise on this issue? – Bikash Bhagat Aug 25 '19 at 16:17
What answer do you expect for string1: lol and string2: lllollll. Is it lllollll or lllllllo? – Venkata Rathnam Aug 25 '19 at 16:36

score 0 · Accepted Answer · answered Aug 30 '19 at 13:34

Finally, found the solution with help of @askipop :

 if(inputStr1 == null || inputStr2 == null){
            return null;
        }

        String res = "";

        HashMap<Character, Integer> hm = new HashMap<>(); 

        for(int i = 0; i < inputStr2.length(); i++){
            Character c = inputStr2.charAt(i);
            if(hm.containsKey(c)){
                hm.put(c, hm.get(c) + 1);
            } else{
                hm.put(c, 1);
            }
        }

        for(int i = 0; i < inputStr1.length(); i++){
            Character ch = inputStr1.charAt(i);
            if(hm.containsKey(ch)){
                res += ch;
                int c = hm.get(ch);
                if (c - 1 > 0){
                    hm.put(ch, c - 1);
                } else{
                    hm.remove(ch);
                }
            }
        }

        if(res.length() > 0){
            return res;
        }

        return null;
    }

Find the intersection of two strings in which characters appearing in both strings are returned (same sequence order as 1st String)

2 Answers2