Given two strings str1 and str2, write code to find out if all non-unique elements in str2 are in str1?

Problem

Given two strings str1 and str2, write code to find out if all non-unique elements in str2 are in str1?

Solution

Method 1 - Using hashset on str2 and boolean array or hashset on str2
Break down the problem into two tasks.

i) Finding the non-unique i.e. repeating elements in str 1. Hashing can be used for this purpose.

ii) Finding if all the characters hashed in the first string are available in the second string. You can use a bool flag array for this purpose

Java code

public static Set<String> getNonUniqueChar(String str1, String str2){  
 HashMap<Character, Integer> visit = new HashMap<Character, Integer>(); // find the non-unique characters  
    HashSet<Character> visit2 = new HashSet<Character>(); // put the st1 chars into to hashset  
    for (int i=0; str2.length; i++) {  
  char c = str2.charAt(i);  
  if(visit.containsKey(c)){  
   Integer charCount = visit.get(c);  
   visit.put(c,charCount++);  
  }else  
   visit.put(c,1);//initially char count is 1  
 }  
           
    for (i=0; i < str1.length; i++){  
  char c = str1.charAt(i);  
        if(!visit2.contains(c))  
   str1.put(c);  
 }  
 //get all the elements where count is greater than 1  
 List<String> nonUniqueCharsinS2 = new ArrayList<String>();  
 for(Character c : visit.keys()) {  
  if(visit.get(c) > 1)  
   nonUniqueCharsinS2.add(c);  
 }  
   
 //iterate on s1 set to get all the elements  
 Set<String> answer = new HashSet<String>();  
    for (Character c : nonUniqueCharsinS2 )  
         if(visit2.contains(c))  
   answer.add(c);  
       
  return answer;  
}  

Time complexity - O(n)
Space complexity - O(n)


See also