Problem Description
Given a string allowed and an array of words, determine how many words are consistent. A word is considered consistent if every character in the word appears in allowed.
Key Insights
- Convert the allowed string into a data structure (like a set) for fast lookups.
- For each word in the words array, check each character against the allowed set.
- Increment a count if all characters in the word are allowed.
- The maximum length of any word is small, making the per-word check efficient.
Space and Time Complexity
Time Complexity: O(n * m), where n is the number of words in the array and m is the maximum length of a word. Space Complexity: O(1) if we consider allowed’s size (up to 26 characters) as a constant; otherwise, O(k) where k is the size of allowed.
Solution
The solution uses a simple set-based approach. First, the allowed string is converted into a set to allow constant time lookups. Then, for each word, we iterate over its characters to verify that each one exists in the allowed set. If all characters in a word are found in the allowed set, we count that word as consistent. This solution efficiently checks each word using the fast membership-check property of sets.