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)

Read More

Given two strings A and B, how would you find out if the characters in B were a subset of the characters in A?

Here is a code in c:

#include <stdio .h>
#include <conio .h>

int isSubset(char *a, char *b);
int main(){

 char str1[]="defabc";
 char str2[]="abcfed";

 if(isSubset(str1, str2)==0)
   printf("\nYes, characters in B=[%s] are a subset of characters in A=[%s]\n",str2,str1);
 }
 else
 {
   printf("\nNo, characters in B=[%s] are not a subset of characters in A=[%s]\n",str2,str1);
 }
 getch();
 return(0);
}

// Function to check if characters in "b" are a subset
// of the characters in "a"
int isSubset(char *a, char *b)
{
 int letterPresent[256];
 int i;
 for(i=0; i<256; i++)
    letterPresent[i]=0;
 
 for(i=0; a[i]!='\0'; i++)
    letterPresent[a[i]]++;
 
 for(i=0; b[i]!='\0'; i++)
    if(!letterPresent[b[i]])
       return(1);
 return(0);
}

same code can be achieved in java by using hashset or array of 256 char as well.

Read More