Remove characters from the second string which are present in the first string

Question

I have written a program to remove the characters from the second string which are present in the first string. The complexity comes out to be BigO(n^2). Can the complexity be further reduced?

public class Tmp {

    public static void main(String[] args) {
        String s = "halloween";
        String s1 = "halcyon";
        char[] ss = s.toCharArray();
        char[] ss1 = s1.toCharArray();

        for(int i=0;i<ss.length;i++){
          for(int j=0;j<ss1.length;j++){
                if(ss1[j] == ss[i]){
                    ss1[j] = 'x'; //Replace the common char with x
                }
            }
         }
        System.out.println(Arrays.toString(ss1));
    }
}

OUTPUT

 [x, x, x, c, y, x, x]

Answer 1

1. Convert first string into a Map. O(N)
2. iterate over other string and check if character present in Map from step 1. O(N) + O(1)

Total time complexity = O(N)

Here you have additional space complexity to store MAP.

Answer 2

You can choose to convert second string to HashSet (if there are no duplicate letters in second string). Then check existence of each letter from first string in hashmap and remove if found.

O(N) complexity for traversing the String array and complexity of put/get in HashSet is almost O(1).

Answer 3

You can have a boolean array of size 26 if all the characters in the source string are small letters. Then scan the source string from start to end and update the boolean array if the character is present. Then scan the target string and check with the boolean array if its present in source array or not.

The complexity will be equal to sum of both strings' length.

Answer 4

Remove characters from input string that are present in mask string

public class RemoveCharacterFromFisrtStringWhichPInSecondString {

    public static void removeCharactersFromFirstString(String str1,String str2){
        StringBuilder sb = new StringBuilder(str1.toLowerCase());
        char maskArray[] = populateMaskArray(str2);
        for(int i=0;i<str1.length();i++){
            char ch = str1.toLowerCase().charAt(i);
            int index = sb.toString().indexOf(ch);
            if(maskArray[ch] == ch) {
                sb.deleteCharAt(index);
            }
        }
        System.out.println(sb.toString());
    }

    /**
     * Time Complexity: O(m) Where m is the length of mask string.
     */
    static char[] populateMaskArray(String mask) {
        char[] array = new char[256];
        for(int i = 0; i < mask.length(); i++) {
            array[mask.charAt(i)] = mask.charAt(i);
        }
        return array;
    }

    public static void main(String[] args) {
        String str1 = "India is country";
        String str2 = "in";
        removeCharactersFromFirstString(str1,str2);

    }

}

Answer 5

public class Test{  
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str,sbstr;
        
        System.out.println("Enter the first String : ");
        str = sc.nextLine();
        
        System.out.println("Enter the second String : ");
        sbstr = sc.nextLine();
        
        char [] c1str = str.toCharArray();
        char [] c2sbstr = sbstr.toCharArray();
       
        
            for(int j=0;j<c2sbstr.length;j++) {
                for(int i=0;i<c1str.length;i++) {

                if(c1str[i] == c2sbstr[j]) {
                    c1str[i] = 0;
                }    
            }
        }

        System.out.println("After removing the characters of second string from first string :");

        for(int i=0;i<c1str.length;i++) {
            System.out.print(c1str[i]); 
        }  
    }
}

Answer 6

 public static String removeCharAt(String s, int pos) {
      return s.substring(0, pos) + s.substring(pos + 1);
   }
 public static void main(String[] args) {
        String s1 = "India is great ";
        s1 = s1.toLowerCase();
        String s2="in";
        
        for (int i = 0; i < s1.length(); i++) {
            for (int j = 0; j < s2.length(); j++) {
                if(s2.charAt(j) == s1.charAt(i)) {
                    s1 = removeCharAt(s1, i);
            }
        }               
    }
        System.out.println(s1);
        
}