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.