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 <= 10⁴
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\).

Python3JavaC++GoTypeScriptRustC

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)

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

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

int countConsistentStrings(char* allowed, char** words, int wordsSize) {
    int n = strlen(allowed);
    int make[26] = {0};
    for (int i = 0; i < n; i++) {
        make[allowed[i] - 'a'] = 1;
    }
    int ans = wordsSize;
    for (int i = 0; i < wordsSize; i++) {
        char* word = words[i];
        for (int j = 0; j < strlen(word); j++) {
            if (!make[word[j] - 'a']) {
                ans--;
                break;
            }
        }
    }
    return ans;
}

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