1684. Count the Number of Consistent Strings

Description

Given a string allowed consisting of distinct characters and an array of strings words, a word is considered consistent if all characters in the word appear in the string allowed. Your task is to count how many words in the array words are consistent.

For example, if allowed = "abc" and words = ["a", "b", "c", "ab", "ac", "abc", "d"], then the consistent words are ["a", "b", "c", "ab", "ac", "abc"], so the function should return 6.

Intuition

The key observation is that a word is consistent if all of its characters are present in the allowed string. Therefore, we can iterate over each word and check whether all of its characters exist in the set of allowed characters. The count of words satisfying this condition gives the answer.

Approach

1. Preprocess the allowed string: Convert the allowed string into a set of characters for fast lookup. This ensures that checking if a character is allowed happens in constant time.
2. Iterate over the words: For each word in the words list, check if all characters of the word are present in the allowed set. This can be done using a simple iteration or using helper functions like all() in Python.
3. Count consistent words: If all characters of a word are allowed, increment the count.
4. Return the count: After processing all words, return the total number of consistent words.

Complexity

Time Complexity:

• Building the set of allowed characters takes O(L), where L is the length of the allowed string.
• For each word, checking if all characters are allowed takes O(W), where W is the length of the word. In the worst case, iterating through all words takes O(N * M), where N is the number of words and M is the average length of a word.
• Overall, the time complexity is O(N * M + L).

Space Complexity:

• Storing the set of allowed characters takes O(L), where L is the length of the allowed string.
• In addition, space is required to store the words, but it is not counted as additional space because it is part of the input.
• Thus, the space complexity is O(L).

Code

C++

class Solution {
public:
    int countConsistentStrings(string allowed, vector& words) {
        unordered_set allowedSet(allowed.begin(), allowed.end());
        int count = 0;

        for (const string& word : words) {
            bool consistent = true;
            for (char c : word) {
                if (allowedSet.find(c) == allowedSet.end()) {
                    consistent = false;
                    break;
                }
            }
            if (consistent) count++;
        }

        return count;
    }
};

Python

class Solution:
    def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
        allowed_set = set(allowed)
        count = 0

        for word in words:
            if all(c in allowed_set for c in word):
                count += 1

        return count

Java

class Solution {
    public int countConsistentStrings(String allowed, String[] words) {
        Set allowedSet = new HashSet<>();
        for (char c : allowed.toCharArray()) {
            allowedSet.add(c);
        }

        int count = 0;
        for (String word : words) {
            boolean consistent = true;
            for (char c : word.toCharArray()) {
                if (!allowedSet.contains(c)) {
                    consistent = false;
                    break;
                }
            }
            if (consistent) count++;
        }

        return count;
    }
}

JavaScript

var countConsistentStrings = function (allowed, words) {
    let count = 0;
    for (let i = 0; i < words.length; i++) {
        const arr = [...new Set([...Array.from(words[i])])]
        if (!arr.some(el => !allowed.includes(el))) count++;
    };
    return count;
};