Count the Number of Consistent Strings — Problem & Solution
Count the Number of Consistent Strings solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Count the Number of Consistent Strings is an easy coding problem on arrays, strings and hash table, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Arrays, Strings, Hash Table, Bit Manipulation, Counting
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a string allowed of distinct characters and an array of strings words. A string is consistent if every one of its characters appears in allowed.
Return the number of consistent strings in words.
Example 1
Input: allowed = "ab", words = ["ad","bd","aaab","baa","badab"]
Output: 2
Explanation: "aaab" and "baa" use only a and b.
Example 2
Input: allowed = "abc", words = ["a","b","c","ab","ac","bc","abc"]
Output: 7
Example 3
Input: allowed = "cad", words = ["cc","acd","b","ba","bac","bad","ac","d"]
Output: 4
Constraints
1 <= words.length <= 201 <= allowed.length <= 261 <= words[i].length <= 10All characters of allowed are distinct lowercase letters.
Hints for Count the Number of Consistent Strings
Hint 1
Turn
allowedinto a 26-bit mask once.Hint 2
Turn each word into its own mask and check that it introduces no bit outside the allowed mask.
Hint 3
wordMask & ~allowedMask == 0is exactly that test.
How to solve Count the Number of Consistent Strings
Turn allowed into a 26-bit mask; a word is consistent iff its own mask has no bit outside it.
Approach
- Build
allowedMask. - For each word build
wordMaskand count it ifwordMask & ~allowedMask == 0.
Why it works
The mask encodes set membership, and word & ~allowed isolates letters not in the allowed set.
Complexity
- Time —
O(total characters) - Space —
O(1)
Pitfalls
- A hash set works equally well; the mask just avoids allocation.
Reference solution
Python
def countConsistentStrings(allowed: str, words) -> int:
mask = 0
for ch in allowed:
mask |= 1 << (ord(ch) - 97)
count = 0
for w in words:
word_mask = 0
for ch in w:
word_mask |= 1 << (ord(ch) - 97)
if word_mask & ~mask == 0:
count += 1
return countJava
public static int countConsistentStrings(String allowed, String[] words) {
int mask = 0;
for (int i = 0; i < allowed.length(); i++) mask |= 1 << (allowed.charAt(i) - 'a');
int count = 0;
for (String w : words) {
int wordMask = 0;
for (int i = 0; i < w.length(); i++) wordMask |= 1 << (w.charAt(i) - 'a');
if ((wordMask & ~mask) == 0) count++;
}
return count;
}C++
int countConsistentStrings(string allowed, vector<string>& words) {
int mask = 0;
for (char c : allowed) mask |= 1 << (c - 'a');
int count = 0;
for (const string& w : words) {
int wordMask = 0;
for (char c : w) wordMask |= 1 << (c - 'a');
if ((wordMask & ~mask) == 0) count++;
}
return count;
}JavaScript
var countConsistentStrings = function(allowed, words) {
let mask = 0;
for (let i = 0; i < allowed.length; i++) mask |= 1 << (allowed.charCodeAt(i) - 97);
let count = 0;
for (let i = 0; i < words.length; i++) {
let wordMask = 0;
for (let j = 0; j < words[i].length; j++) wordMask |= 1 << (words[i].charCodeAt(j) - 97);
if ((wordMask & ~mask) === 0) count++;
}
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.