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

Question

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.

Lunch

This looks like a homework problem; but you could simply create hashsets for both strings and use containsAll – Exoergic

Answer 1

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.

Protolithic

If stringA is significantly longer than stringB, couldn't the conversion slow down the process in the long run? – Nimwegen

@Nerdizzle: Yes, it's possible for specific cases to be slower using this approach. – Protolithic

Couldn't you just create two hashsets and use containsAll()? – Exoergic

@NullUserException: You could do that. It has the same time complexity. – Protolithic

You could use a hashset with initial size set at stringA.length() and compaction factor of 1F, then do a Collections.addAll(hashset,stringA.toCharArray()), that would give you your hashset w/o the wait of having to expand it – Wessex

Interesting approuch. I would be interested if the use of a bitset might improve this. Where either the value of the char, or the position in a predefined alphabet/charScheme determines the position/offset in the BitSet. If there are limited characters allowed (e.g. only alphabet for example) it might be a bit more effecient than the use of a HasSet. – Stannum

I understand the process time of "string to hashset" conversion is O(1), but it is pretty long in practical case. (I measure the process time by comparing the time before and after the conversion). Is there a problem with my measuring method? Or this is a theory and my concern is not valid? – Lunch

String to hashset is not O(1). It's proportional to the length of the string. After the string is constructed, membership tests are O(1). This analysis is theoretical, and would be most observable with very large strings. (10000 characters or more) To offer practical performance advice, we'd need to know more about your use case. – Protolithic