Count the Number of Consistent Strings

Count the Number of Consistent Strings

What is this problem about?

The Count the Number of Consistent Strings coding problem involves a string of "allowed" characters and an array of target "words." A word is considered "consistent" if every character in the word appears in the "allowed" string.

Your task is to return the total number of consistent strings in the list.

Why is this asked in interviews?

This is a standard "Easy" problem used by Amazon and Google to test basic hash table interview pattern and string interview pattern skills. It evaluations a candidate's ability to perform efficient lookups. While a simple string search works, using a boolean array or a set for the allowed characters shows an understanding of time complexity ($O(1)$ lookup vs. $O(M)$ search).

Algorithmic pattern used

This problem is best solved using a Frequency Map (Hash Set) or a Bitmask.

1. Store all characters from the allowed string in a Hash Set (or a boolean array of size 26).
2. For each word in the list:
   • Iterate through its characters.
   • If any character is not in the set, the word is not consistent.
   • If you finish the word and all characters were present, increment the count.

Example explanation

allowed = "abc", words = ["a", "b", "ab", "abd", "e"]

1. Set = {a, b, c}.
2. Word "a": 'a' is in set. Consistent.
3. Word "b": 'b' is in set. Consistent.
4. Word "ab": 'a' and 'b' are in set. Consistent.
5. Word "abd": 'd' is NOT in set. Inconsistent.
6. Word "e": 'e' is NOT in set. Inconsistent. Total count = 3.

Common mistakes candidates make

• Inefficient lookups: Using allowed.contains(char) inside the loop without converting allowed to a set first, leading to $O(W imes L imes A)$ complexity instead of $O(W imes L + A)$.
• Empty strings: Not handling the case where allowed is empty (though usually constraints prevent this).
• Case sensitivity: Not confirming if the characters are all lowercase or mixed case.

Interview preparation tip

For problems involving a small, fixed set of characters (like the 26 English letters), a boolean array bool[26] or a bitmask integer is often faster and more memory-efficient than a Hash Set. This optimization is a nice "extra" to mention to your interviewer.