Code Implementation

class Solution:
    def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
        allowed_set = set(allowed)
        count = 0
        for word in words:
            if all(char in allowed_set for char in word):
                count += 1
        return count
      

class Solution {
   public:
    int countConsistentStrings(string allowed, vector<string>& words) {
        unordered_set<char> 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;
    }
};
      

class Solution {
    public int countConsistentStrings(String allowed, String[] words) {
        Set<Character> 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;
    }
}
      

var countConsistentStrings = function(allowed, words) {
    const allowedSet = new Set(allowed);
    let count = 0;
    for (const word of words) {
        let consistent = true;
        for (const char of word) {
            if (!allowedSet.has(char)) {
                consistent = false;
                break;
            }
        }
        if (consistent) count++;
    }
    return count;
};
      

Problem Description

Given a string allowed consisting of distinct lowercase English letters, and an array of strings words, your task is to count how many words in words are consistent.
A word is considered consistent if every character in the word appears in the allowed string.
Key constraints:

• Each character in allowed can be used any number of times (no reuse restriction).
• Each word is checked independently.
• You must count the number of consistent words, not return the words themselves.

Thought Process

The core of this problem is to verify, for each word, whether all its letters are present in the allowed set.
At first, one might think of checking each character of every word against the allowed string using a loop. However, this approach could be slow if allowed or the words are long, as checking membership in a string is O(N).
To optimize, we can quickly check if a character is in allowed by converting allowed to a set (or hash set/map) for O(1) lookups.
The process is: for each word, check every character. If all are in allowed, increment the count.
This is a classic case of moving from a brute-force (nested loops, slow lookups) to an optimized approach using a set for fast membership checking.

Solution Approach

• Step 1: Convert the allowed string into a set or hash set. This allows us to check if a character is allowed in constant time.
• Step 2: Initialize a counter to zero. This will keep track of the number of consistent strings found.
• Step 3: Iterate through each word in the words array:
  • For each word, check every character.
  • If any character in the word is not in the allowed set, mark the word as inconsistent and move to the next word.
  • If all characters are allowed, increment the counter.
• Step 4: After processing all words, return the counter as the final result.

We use a set for allowed because:

• Set membership checks are O(1) on average.
• It is easy to construct and requires only a single pass through allowed.

Example Walkthrough

Example:
allowed = "ab"
words = ["ad","bd","aaab","baa","badab"]

Let's walk through each word:

• "ad": 'a' is allowed, 'd' is not. Not consistent
• "bd": 'b' is allowed, 'd' is not. Not consistent
• "aaab": 'a' and 'b' are both allowed. Consistent
• "baa": 'b' and 'a' are allowed. Consistent
• "badab": 'b' and 'a' are allowed, but 'd' is not. Not consistent

Time and Space Complexity

• Brute-force approach:
  • For each word, for each character, check if it is in allowed (as a string). Each check is O(L), where L is the length of allowed.
  • Total time: O(N * M * L), where N = number of words, M = average word length, L = length of allowed.
• Optimized approach:
  • Convert allowed to a set: O(L).
  • For each word, for each character, check if in set: O(1) per check.
  • Total time: O(L) + O(N * M).
  • Space: O(L) for the set.

The optimized approach is much faster, especially for large inputs, because set lookups are constant time.

Summary

To solve the "Count the Number of Consistent Strings" problem, we leveraged a set for fast character lookups. This allowed us to efficiently check each word for consistency with the allowed string. The key insight was to use data structures that offer constant time membership checks, reducing overall complexity and making the solution scalable and elegant.