CC-15 : Find the extra character.

Description:

Given two similar Strings str1 and str2, find the extra character that is present in str2.

Test cases and expected outputs:

Input Parameters	Expected outputs
str1="rare"; str2="arere";	The additional character in str2 is e
str1="contains"; str2="saitnocns";	The additional character in str2 is s
str1="metal"; str2="telmaz";	The additional character in str2 is z

Pseudocode:

The java method should accept following input parameters: str1(String), str2(String).

Initialize a variable str1FreqMap of type HashMap to hold str1’s characters as keys, and the frequency of these characters as the values.

Iterate through str1 using a for loop with idx as a loop variable with initial value 0 and increment idx till it reaches str1.length()-1:

If str1FreqMap does not contain key str1.CharAt(idx), then put key-value pair str1.CharAt(idx) and 1 to str1FreqMap.

If str1FreqMap contains key str1.CharAt(idx) with value freq, then put key-value pair str1.CharAt(idx) and freq+1 to str1FreqMap.

Initialize a variable str2FreqMap of type HashMap to hold str2’s characters as keys, and the frequency of these characters as the values.

Iterate through str2 using a for loop with idx as a loop variable with initial value 0 and increment idx till it reaches str2.length()-1:

If str2FreqMap does not contain key str2.CharAt(idx), then put key-value pair str2.CharAt(idx) and 1 to str2FreqMap

If str2FreqMap contains key str2.CharAt(idx) with value freq, then put key-value pair str2.CharAt(idx) and freq+1 to str2FreqMap.

After above loop completes, iterate through keys of str2FreqMap and extract corresponding values for keys from str2FreqMap and str1FreqMap. If the count of value for a particular key is more for str2FreqMap than the value from str1FreqMap, then this current key is the extra key in str2. Return this extra current key from the program.

Code:

public char hashMapFindDifference(String str1, String str2) throws Exception{
	HashMap<Character,Integer> str1FreqMap=new HashMap<Character, Integer>();
	for (int idx=0; idx < str1.length(); idx++) {
		str1FreqMap.put(str1.charAt(idx), str1FreqMap.getOrDefault(str1.charAt(idx),0)+1);
	}
	HashMap<Character,Integer> str2FreqMap=new HashMap<Character, Integer>();
	for (int idx=0; idx < str2.length(); idx++) {
		str2FreqMap.put(str2.charAt(idx), str2FreqMap.getOrDefault(str2.charAt(idx),0)+1);
	}
	Iterator<Character> itr=str2FreqMap.keySet().iterator();
	while (itr.hasNext()) {
		char c=itr.next();
		int cnt2=str2FreqMap.get(c);
		int cnt1=str1FreqMap.getOrDefault(c,0);
		if (cnt2==cnt1+1) {
			return c;
		}
	}		
	return '\u0020';		
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

import java.util.HashMap;
import java.util.Iterator;


public class HashMapFindDifference {
	
public char hashMapFindDifference(String str1, String str2) throws Exception{
	HashMap<Character,Integer> str1FreqMap=new HashMap<Character, Integer>();
	for (int idx=0; idx < str1.length(); idx++) {
		str1FreqMap.put(str1.charAt(idx), str1FreqMap.getOrDefault(str1.charAt(idx),0)+1);
	}
	HashMap<Character,Integer> str2FreqMap=new HashMap<Character, Integer>();
	for (int idx=0; idx < str2.length(); idx++) {
		str2FreqMap.put(str2.charAt(idx), str2FreqMap.getOrDefault(str2.charAt(idx),0)+1);
	}
	Iterator<Character> itr=str2FreqMap.keySet().iterator();
	while (itr.hasNext()) {
		char c=itr.next();
		int cnt2=str2FreqMap.get(c);
		int cnt1=str1FreqMap.getOrDefault(c,0);
		if (cnt2==cnt1+1) {
			return c;
		}
	}		
	return '\u0020';		
}
	
	
    
public static void main(String[] args) {
		
	HashMapFindDifference hp=new HashMapFindDifference();
	char retVal;
	try {
	String str1="rare";
	String str11="arere";
	System.out.println("\n\nThe char array  is: "+str1);
	System.out.println("\n\nThe target String is: "+str11);
	retVal=hp.hashMapFindDifference(str1, str11);
	System.out.println("The addtional character in str2 is "+retVal);
			
			
	str1="contains";
	str11="saitnocns";
	System.out.println("\n\nThe char array  is: "+str1);
	System.out.println("\n\nThe target String is: "+str11);
	retVal=hp.hashMapFindDifference(str1, str11);
	System.out.println("The addtional character in str2 is "+retVal);
			
	str1="metal";
	str11="telmaz";
	System.out.println("\n\nThe char array  is: "+str1);
	System.out.println("\n\nThe target String is: "+str11);
	retVal=hp.hashMapFindDifference(str1, str11);
	System.out.println("The addtional character in str2 is "+retVal);
			
	str1="deer";
	str11="reeed";
	System.out.println("\n\nThe char array  is: "+str1);
	System.out.println("\n\nThe target String is: "+str11);
	retVal=hp.hashMapFindDifference(str1, str11);
	System.out.println("The addtional character in str2 is "+retVal);
						
						
	}catch (Exception exception) {
	System.out.print("Exception: "+ exception);
	}
				
}

}