Count the Number of Consistent Strings - Video Solutions

Problem Overview: You receive a string allowed and an array of strings words. A word is consistent if every character in the word appears in allowed. The task is to count how many words satisfy this condition.

Approach 1: Using Set for Allowed Characters (O(n * m) time, O(1) space)

Store all characters from allowed in a hash set for constant-time membership checks. Iterate through each word in words, and for every character verify that it exists in the set. If any character is missing, mark the word as inconsistent and skip it. Hash lookups are O(1), so each word takes time proportional to its length. This approach relies on a hash table and works well because the alphabet size is small and lookups are extremely fast.

Approach 2: Using Bitmasking (O(n * m) time, O(1) space)

Instead of a set, encode the allowed characters into a 26-bit integer mask. Each bit represents whether a letter from 'a' to 'z' is allowed. While scanning a word, compute the bit for each character and check if that bit exists in the mask using a bitwise AND operation. If a character's bit is not set, the word is inconsistent. This approach leverages bit manipulation to replace hash lookups with fast bit operations. It uses constant memory and performs well when you want minimal overhead.

Both strategies iterate through the string characters of every word and validate them against the allowed set. Since each character is processed once, the runtime scales linearly with the total number of characters across all words.

Recommended for interviews: The hash set solution is the most commonly expected answer because it is simple and readable. It demonstrates proper use of constant-time lookups. The bitmasking version is a strong follow-up optimization that shows deeper understanding of character encoding and low-level operations.