Count the Number of Consistent Strings
EasyPrompt
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 <= 10- The characters in
allowedare distinct. words[i]andallowedcontain only lowercase English letters.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach iterates through each word and, for each character in the word, performs a linear search within the allowed string to check for its existence. This is the most straightforward but least efficient method.
Algorithm
- Initialize
count = 0. - For each
wordinwords:- Set a flag
is_consistent = true. - For each character
cinword:- If
cis not found inallowed(using a linear search likeString.indexOf()):- Set
is_consistent = false. - Break the inner loop.
- Set
- If
- If
is_consistentistrue, incrementcount.
- Set a flag
- Return
count.
Walkthrough
The brute-force method directly translates the problem statement into code. We initialize a counter for consistent strings. Then, we iterate through each word in the input array words. For each word, we assume it's consistent and then check every one of its characters. The check involves searching for the character in the allowed string. A simple way to do this is with the String.indexOf() method. If indexOf() returns -1, it means the character is not present in allowed, so the word is not consistent. We can then stop checking the current word and move to the next. If we finish checking all characters of a word and haven't found any unallowed ones, we increment our counter.
class Solution { public int countConsistentStrings(String allowed, String[] words) { int consistentCount = 0; for (String word : words) { boolean isConsistent = true; for (char c : word.toCharArray()) { if (allowed.indexOf(c) == -1) { isConsistent = false; break; } } if (isConsistent) { consistentCount++; } } return consistentCount; }}Complexity
Time
O(N * M * K), where N is the number of words, M is the maximum length of a word, and K is the length of the `allowed` string. For each of the M characters in each of the N words, we perform a linear scan of the `allowed` string, which takes O(K) time.
Space
O(1), as we only use a few variables to keep track of the count and state. No extra space proportional to the input size is used.
Trade-offs
Pros
Simple to understand and implement.
Requires no extra data structures, leading to O(1) space complexity.
Cons
Highly inefficient for larger inputs, especially with a long
allowedstring, due to the nested loops and the O(K) check for each character.
To improve the lookup time for allowed characters, we can pre-process the allowed string and store its characters in a HashSet. This allows for checking if a character is allowed in average O(1) time, significantly speeding up the process compared to a linear search.
Algorithm
- Create a
HashSetnamedallowed_set. - For each character
cinallowed, addctoallowed_set. - Initialize
count = 0. - For each
wordinwords:- Set a flag
is_consistent = true. - For each character
cinword:- If
allowed_setdoes not containc(an O(1) average time check):- Set
is_consistent = false. - Break the inner loop.
- Set
- If
- If
is_consistentistrue, incrementcount.
- Set a flag
- Return
count.
Walkthrough
The bottleneck in the brute-force approach is the repeated linear search in the allowed string. We can optimize this by using a data structure that provides fast lookups. A HashSet is ideal for this. First, we iterate through the allowed string once and populate a HashSet with its characters. This setup step takes time proportional to the length of allowed. After that, for each character in each word, we can check for its presence in the HashSet in average O(1) time. The rest of the logic remains the same: iterate through words, check each character, and if an unallowed character is found, move to the next word. If a word passes all checks, increment the count.
import java.util.HashSet;import java.util.Set; class Solution { public int countConsistentStrings(String allowed, String[] words) { Set<Character> allowedChars = new HashSet<>(); for (char c : allowed.toCharArray()) { allowedChars.add(c); } int consistentCount = 0; for (String word : words) { boolean isConsistent = true; for (char c : word.toCharArray()) { if (!allowedChars.contains(c)) { isConsistent = false; break; } } if (isConsistent) { consistentCount++; } } return consistentCount; }}Complexity
Time
O(K + N * M), where K is the length of `allowed`, N is the number of words, and M is the maximum length of a word. It takes O(K) to build the set and O(N * M) to iterate through all characters of all words with O(1) lookups.
Space
O(K), for storing the K characters of the `allowed` string in a `HashSet`. Since K is at most 26, this is effectively O(1) constant space.
Trade-offs
Pros
Much more efficient than the brute-force approach due to O(1) lookups.
The logic remains clear and readable.
Cons
Uses extra space for the HashSet.
There can be a slight overhead associated with hashing compared to direct array access or bitwise operations.
This approach leverages bitwise operations for maximum efficiency. Since the input is restricted to 26 lowercase English letters, we can represent the set of allowed characters using a single 32-bit integer, known as a bitmask. Each bit from 0 to 25 corresponds to a letter 'a' through 'z'. This makes checking for an allowed character an extremely fast bitwise operation.
Algorithm
- Initialize an integer
mask = 0. - For each character
cinallowed:- Set the bit corresponding to
c:mask = mask | (1 << (c - 'a')).
- Set the bit corresponding to
- Initialize
count = 0. - For each
wordinwords:- Set a flag
is_consistent = true. - For each character
cinword:- Check if the bit for
cis set inmaskusing(mask & (1 << (c - 'a'))). - If the result is 0, the character is not allowed.
- Set
is_consistent = false. - Break the inner loop.
- Set
- Check if the bit for
- If
is_consistentistrue, incrementcount.
- Set a flag
- Return
count.
Walkthrough
Given that the character set is small and fixed (26 lowercase letters), we can use a bitmask as a highly efficient alternative to a HashSet or a boolean array. We use a single integer where each of the first 26 bits represents a letter of the alphabet. We first create this allowedMask by iterating through the allowed string. For each character, we set its corresponding bit to 1. Then, when we check the characters of each word, we can determine if a character is allowed by checking if its corresponding bit is set in the allowedMask. This check is done using a bitwise AND operation, which is extremely fast at the hardware level.
class Solution { public int countConsistentStrings(String allowed, String[] words) { int allowedMask = 0; for (char c : allowed.toCharArray()) { allowedMask |= (1 << (c - 'a')); } int consistentCount = 0; for (String word : words) { boolean isConsistent = true; for (char c : word.toCharArray()) { // Check if the bit for the character is NOT set in the mask if ((allowedMask & (1 << (c - 'a'))) == 0) { isConsistent = false; break; } } if (isConsistent) { consistentCount++; } } return consistentCount; }}Complexity
Time
O(K + N * M), where K is the length of `allowed`, N is the number of words, and M is the maximum length of a word. The time complexity is asymptotically the same as the HashSet approach, but bitwise operations are generally faster than hash lookups at the machine level.
Space
O(1), as we only use a single integer for the bitmask, regardless of the input size.
Trade-offs
Pros
Extremely fast due to efficient bitwise operations.
Minimal space usage (a single integer), making it the most space-efficient solution.
The most optimal solution for the given constraints.
Cons
The logic might be slightly less intuitive for those unfamiliar with bitmasking.
Solutions
Solution
class Solution {public int countConsistentStrings(String allowed, String[] words) { boolean[] s = new boolean[26]; for (char c : allowed.toCharArray()) { s[c - 'a'] = true; } int ans = 0; for (String w : words) { if (check(w, s)) { ++ans; } } return ans; }private boolean check(String w, boolean[] s) { for (int i = 0; i < w.length(); ++i) { if (!s[w.charAt(i) - 'a']) { return false; } } return true; }}class Solution {public: int countConsistentStrings(string allowed, vector<string> &words) { bitset<26> s; for (auto &c : allowed) s[c - 'a'] = 1; int ans = 0; auto check = [&](string &w) { for (auto &c : w) if (!s[c - 'a']) return false; return true; }; for (auto &w : words) ans += check(w); return ans; }};class Solution : def countConsistentStrings ( self , allowed : str , words : List [ str ]) -> int : s = set ( allowed ) return sum ( all ( c in s for c in w ) for w in words )Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.