Search code examples
javacomparesubsetcomplexity-theorycomputation

Find whether each character in 1 string is exist in another string, faster than O(n^2)

Given that 2 strings:

String stringA = "WHATSUP";
String stringB = "HATS";

I want to find out whether each character in stringB H A T S exists in stringA

In a junior approach, the process can be done within a nested for-loop which its computation complexity is O(n^2).

for(int i = 0; i < stringA.length(); i++){
    for(int j = 0; j < stringB.length(); j++){
        if(stringA.charAt(i) == stringB.charAt(j))
            //do something
    }
}

I am looking for a faster solution to solve this problem.

Solution

  • There is a linear time algorithm.

    1. Convert your stringA to a hash-set of characters that has O(1) membership testing.
    2. Iterate over each character in stringB.
    3. If one of the characters isn't in your hash-set, the test fails.
    4. If there is no failure, the test succeeds.