Count the Number of Consistent Strings

Difficulty: Easy | Acceptance: 88.50% | Paid: No Topics: Array, Hash Table, String, Bit Manipulation, Counting

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.

Table of Contents

• Examples
• Constraints
• Brute Force
• Hash Set
• Boolean Array
• Bit Manipulation

Examples

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
allowed consists of distinct lowercase English letters.
words[i] consists of lowercase English letters.

Brute Force

Intuition For every word, iterate through its characters and check if each character exists within the allowed string using a built-in search function.

Steps

• Initialize a counter to 0.
• Iterate through each word in the words array.
• For each word, iterate through each character.
• Check if the character is present in the allowed string.
• If any character is not found, the word is not consistent; skip to the next word.
• If all characters are found, increment the counter.

class Solution:
    def countConsistentStrings(self, allowed: str, words: list[str]) -> int:
        count = 0
        for word in words:
            is_consistent = True
            for char in word:
                if char not in allowed:
                    is_consistent = False
                    break
            if is_consistent:
                count += 1
        return count

Complexity

• Time: O(N * M * L), where N is the number of words, M is the average length of a word, and L is the length of allowed (max 26). In the worst case, checking char in allowed takes O(L).
• Space: O(1)
• Notes: Simple to implement but slower due to repeated string scanning.

Hash Set

Intuition Optimize the lookup process by storing the characters of allowed in a Hash Set. This allows for O(1) average time complexity for checking if a character is allowed.

Steps

• Convert the allowed string into a Set of characters.
• Initialize a counter to 0.
• Iterate through each word in words.
• For each word, iterate through its characters.
• Check if every character exists in the Set.
• If all characters are present, increment the counter.

class Solution:
    def countConsistentStrings(self, allowed: str, words: list[str]) -> int:
        allowed_set = set(allowed)
        count = 0
        for word in words:
            is_consistent = True
            for char in word:
                if char not in allowed_set:
                    is_consistent = False
                    break
            if is_consistent:
                count += 1
        return count

Complexity

• Time: O(N * M), where N is the number of words and M is the average length of a word. Set lookups are O(1) on average.
• Space: O(1), as the set stores at most 26 characters.
• Notes: Very efficient and idiomatic for high-level languages.

Boolean Array

Intuition Since the input consists only of lowercase English letters, we can use a fixed-size boolean array of length 26 to track allowed characters. This avoids the overhead of hashing and is generally faster for small, fixed key sets.

Steps

• Create a boolean array of size 26 initialized to false.
• Iterate through allowed and set the corresponding index (e.g., char - 'a') to true.
• Iterate through words and their characters.
• Check the boolean array for each character.
• Count words where all characters map to true.

class Solution:
    def countConsistentStrings(self, allowed: str, words: list[str]) -> int:
        allowed_chars = [False] * 26
        for char in allowed:
            allowed_chars[ord(char) - ord('a')] = True
        
        count = 0
        for word in words:
            is_consistent = True
            for char in word:
                if not allowed_chars[ord(char) - ord('a')]:
                    is_consistent = False
                    break
            if is_consistent:
                count += 1
        return count

Complexity

• Time: O(N * M), where N is the number of words and M is the average length of a word.
• Space: O(1), fixed size array of 26 booleans.
• Notes: Extremely fast due to direct memory access and lack of hashing overhead.

Bit Manipulation

Intuition We can represent the set of allowed characters using a 26-bit integer (bitmask). Each bit corresponds to a letter in the alphabet (e.g., bit 0 for ‘a’, bit 1 for ‘b’). A word is consistent if its bitmask is a subset of the allowed bitmask.

Steps

• Initialize an integer mask to 0.
• Iterate through allowed, setting the corresponding bit in mask (e.g., mask |= 1 << (c - 'a')).
• Iterate through each word in words.
• For each word, calculate its own bitmask wordMask.
• Check if (wordMask & mask) == wordMask. If true, all bits in wordMask are set in mask.
• Increment count if the condition holds.

class Solution:
    def countConsistentStrings(self, allowed: str, words: list[str]) -> int:
        mask = 0
        for char in allowed:
            mask |= 1 << (ord(char) - ord('a'))
        
        count = 0
        for word in words:
            word_mask = 0
            for char in word:
                word_mask |= 1 << (ord(char) - ord('a'))
            if (word_mask & mask) == word_mask:
                count += 1
        return count

Complexity

• Time: O(N * M), where N is the number of words and M is the average length of a word.
• Space: O(1), using only a few integer variables.
• Notes: Highly efficient for space and often very fast, commonly used in competitive programming for alphabet-related problems.