## Wednesday, July 30, 2014

### 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)