You are given a string allowed consisting of distinct characters and an array of strings words. A string is consistent if all characters in the string appear in the string allowed.
Return the number of consistent strings in the array words.
Example 1:
Input: allowed = "ab", words = ["ad","bd","aaab","baa","badab"] Output: 2 Explanation: Strings "aaab" and "baa" are consistent since they only contain characters 'a' and 'b'.
Example 2:
Input: allowed = "abc", words = ["a","b","c","ab","ac","bc","abc"] Output: 7 Explanation: All strings are consistent.
Example 3:
Input: allowed = "cad", words = ["cc","acd","b","ba","bac","bad","ac","d"] Output: 4 Explanation: Strings "cc", "acd", "ac", and "d" are consistent.
Constraints:
1 <= words.length <= 1041 <= allowed.length <= 261 <= words[i].length <= 10allowed are distinct.words[i] and allowed contain only lowercase English letters.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.
We can leverage the power of sets to efficiently check if a word is consistent with the allowed characters. By converting the string `allowed` into a set, we can perform constant time look-up operations for each character in the words.
We will iterate through each word and check if every character of the word is present in the allowed set. If all characters are present, the word is consistent. Otherwise, it is not. We count the number of consistent words and return it.
This solution first converts the `allowed` string to a set so that we can efficiently check membership of each character. Then it iterates over each word and uses a generator expression to check if all characters in the word are in the `allowed_set`. If a word is consistent, it increments the count of consistent words.
Time Complexity: O(n * m), where n is the number of words and m is the average length of the words.
Space Complexity: O(1), as the space usage is dominated by the set of allowed characters, which is fixed at most 26.
An alternative approach to solve this problem is using bitmasking. We can represent the set of allowed characters as a bitmask, where each bit corresponds to a specific character ('a' could be the least significant bit and 'z' the most significant). This allows us to quickly check if a word is consistent by creating a bitmask of the word and verifying it against the allowed bitmask.
In this Python implementation, we first create a bitmask for the allowed characters. Then, for each word, we convert it into a bitmask and check it against the allowed bitmask using bitwise operations. A word is consistent if its bitmask ANDed with the allowed mask produces the word mask itself.
Time Complexity: O(n * m), where n is the number of words and m is the average length of the words.
Space Complexity: O(1), because we use a constant amount of extra space regardless of input size.
A straightforward approach is to use a hash table or array s to record the characters in allowed. Then iterate over the words array, for each string w, determine whether it is composed of characters in allowed. If so, increment the answer.
The time complexity is O(m), and the space complexity is O(C). Here, m is the total length of all strings, and C is the size of the character set allowed. In this problem, C leq 26.
We can also use a single integer to represent the occurrence of characters in each string. In this integer, each bit in the binary representation indicates whether a character appears.
We simply define a function f(w) that can convert a string w into an integer. Each bit in the binary representation of the integer indicates whether a character appears. For example, the string ab can be converted into the integer 3, which is represented in binary as 11. The string abd can be converted into the integer 11, which is represented in binary as 1011.
Back to the problem, to determine whether a string w is composed of characters in allowed, we can check whether the result of the bitwise OR operation between f(allowed) and f(w) is equal to f(allowed). If so, increment the answer.
The time complexity is O(m), where m is the total length of all strings. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Approach 1: Using Set for Allowed Characters | Time Complexity: O(n * m), where n is the number of words and m is the average length of the words. |
| Approach 2: Using Bitmasking | Time Complexity: O(n * m), where n is the number of words and m is the average length of the words. |
| Hash Table or Array | — |
| Bit Manipulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Set for Allowed Characters | O(n * m) | O(1) | General case. Clean and readable solution with constant-time character checks. |
| Bitmasking | O(n * m) | O(1) | When optimizing memory or demonstrating bit manipulation skills. |
Count the Number of Consistent Strings - Leetcode 1684 - Python • NeetCodeIO • 7,968 views views
Watch 9 more video solutions →Practice Count the Number of Consistent Strings with our built-in code editor and test cases.
Practice on FleetCode