Tricky Java Strings Interview Q. Given List<String> and char [] return longest string containing only char []

Question

Given a List of Strings and an array of characters, return the longest String that contains only characters in the array.

I'm pretty sure I hosed it up. My first instinct was to use a regular expression but I don't think anybody gets those right the first time and without looking anything up.

Is there a tricky way of doing this using bitwise operators or something?

Answer 1

One idea would be to convert the char[] to a Set<Character> for O(1) containment tests, then simply loop over the list of strings and check if each particular string has only characters contained in the aforementioned set, keeping track of the longest string you find with this property.

If you have more information, you could make more optimizations. For example, if the strings themselves are very long but the list isn't, it might be beneficial to sort the list by length first, then start processing the strings longest first.

---

Is there a tricky way of doing this using bitwise operators or something?

If you have some sort of (small-ish) limit on the range of character that can be included in the char[], then you could potentially encode the whole thing in a single int/long, which would be a substitute for the Set<Character> I mentioned above. For example, let's say that only the characters from 'a' to 'z' will be included, then we can perform the encoding as follows:

long charset = 0;

for (char c : chars) {
    charset |= (1 << (c - 'a'));
}

Now, to check if some character c was contained in the original char[], we can simply use:

if ((charset & (1 << (c - 'a'))) != 0) {
    // c was in the original char[]
}