Count the Number of Consistent Strings
Problem
Given an allowed string of distinct lowercase letters and a list of words, count how many words consist only of allowed letters.
allowed = "ab", words = ["ad","bd","aaab","baa","badab"]2def count_consistent_strings(allowed, words):
mask = 0
for c in allowed:
mask |= 1 << (ord(c) - ord('a'))
cnt = 0
for w in words:
wmask = 0
for c in w:
wmask |= 1 << (ord(c) - ord('a'))
if (wmask & ~mask) == 0:
cnt += 1
return cntfunction countConsistentStrings(allowed, words) {
let mask = 0;
for (const c of allowed) mask |= 1 << (c.charCodeAt(0) - 97);
let cnt = 0;
for (const w of words) {
let wm = 0;
for (const c of w) wm |= 1 << (c.charCodeAt(0) - 97);
if ((wm & ~mask) === 0) cnt++;
}
return cnt;
}class Solution {
public int countConsistentStrings(String allowed, String[] words) {
int mask = 0;
for (char c : allowed.toCharArray()) mask |= 1 << (c - 'a');
int cnt = 0;
for (String w : words) {
int wm = 0;
for (char c : w.toCharArray()) wm |= 1 << (c - 'a');
if ((wm & ~mask) == 0) cnt++;
}
return cnt;
}
}int countConsistentStrings(string allowed, vector<string>& words) {
int mask = 0;
for (char c : allowed) mask |= 1 << (c - 'a');
int cnt = 0;
for (auto& w : words) {
int wm = 0;
for (char c : w) wm |= 1 << (c - 'a');
if ((wm & ~mask) == 0) cnt++;
}
return cnt;
}Explanation
Instead of checking each word letter by letter against the allowed set, we squeeze the whole allowed set into a single number called a bitmask. Each of the 26 lowercase letters gets its own bit, so the allowed set becomes one compact integer we can compare against instantly.
We build mask by turning on bit c - 'a' for every allowed letter. Then for each word we build its own wmask the same way. A word is consistent only if every letter it uses is allowed.
The clever check is wmask & ~mask. Here ~mask is the set of forbidden letters (every bit that allowed did not turn on). If the word shares no bit with the forbidden set, the AND is 0, meaning the word is clean and we count it.
Example: allowed = "ab" gives mask with bits a and b on. The word "baa" uses only a and b, so wmask & ~mask == 0 and it counts. The word "ad" uses d, which is a forbidden bit, so the AND is nonzero and it is skipped.
Because each letter is one bit, the per-word check is just one fast AND, and we only walk through all the characters once.