# 1684. Count the Number of Consistent Strings

## Description

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 <= 104
• 1 <= allowed.length <= 26
• 1 <= words[i].length <= 10
• The characters in allowed are distinct.
• words[i] and allowed contain only lowercase English letters.

## Solutions

Solution 1: Hash Table or Array

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$.

Solution 2: Bit Manipulation

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)$.

• 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)


• func countConsistentStrings(allowed string, words []string) (ans int) {
s := [26]bool{}
for _, c := range allowed {
s[c-'a'] = true
}
check := func(w string) bool {
for _, c := range w {
if !s[c-'a'] {
return false
}
}
return true
}
for _, w := range words {
if check(w) {
ans++
}
}
return ans
}

• function countConsistentStrings(allowed: string, words: string[]): number {
const set = new Set([...allowed]);
const n = words.length;
let ans = n;
for (const word of words) {
for (const c of word) {
if (!set.has(c)) {
ans--;
break;
}
}
}
return ans;
}


• impl Solution {
pub fn count_consistent_strings(allowed: String, words: Vec<String>) -> i32 {
let n = words.len();
let mut make = [false; 26];
for c in allowed.as_bytes() {
make[(c - b'a') as usize] = true;
}
let mut ans = n as i32;
for word in words.iter() {
for c in word.as_bytes().iter() {
if !make[(c - b'a') as usize] {
ans -= 1;
break;
}
}
}
ans
}
}