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.
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; }}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.