1684. Count the Number of Consistent Strings - Explanation

1. Brute Force

Intuition

A string is consistent if every character in it appears in the allowed string. The straightforward approach is to check each word character by character. For each character, we scan through the allowed string to see if it exists. If any character is not found, the word is inconsistent.

Algorithm

Initialize a counter res to 0.
For each word in words:
- Set a flag to true (assuming the word is consistent).
- For each character in the word, check if it exists in allowed by scanning through allowed.
- If any character is not found, set the flag to false and break out of the inner loop.
- If the flag is still true after checking all characters, increment res.
Return res.

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

        for w in words:
            flag = 1
            for c in w:
                if c not in allowed:
                    flag = 0
                    break
            res += flag

        return res

Time & Space Complexity

Time complexity: $O(n * m * l)$
Space complexity: $O(1)$

Where $n$ is the number of words, $m$ is the length of the string $allowed$ , and $l$ is the length of the longest word.

2. Hash Set

Intuition

The brute force approach is slow because we scan through allowed for every character lookup. We can speed this up by storing all allowed characters in a hash set, which provides O(1) average lookup time. Instead of counting consistent words, we can start with the total count and subtract whenever we find an inconsistent word.

Algorithm

Convert allowed into a hash set for O(1) character lookups.
Initialize res to the total number of words.
For each word in words:
- For each character in the word, check if it exists in the hash set.
- If any character is not found, decrement res and break out of the inner loop.
Return res.

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

        res = len(words)
        for w in words:
            for c in w:
                if c not in allowed:
                    res -= 1
                    break

        return res

Time & Space Complexity

Time complexity: $O(n * l + m)$
Space complexity: $O(m)$

Where $n$ is the number of words, $m$ is the length of the string $allowed$ , and $l$ is the length of the longest word.

3. Boolean Array

Intuition

Since we are only dealing with lowercase English letters (26 characters), we can use a boolean array of size 26 instead of a hash set. Each index represents a letter ('a' = 0, 'b' = 1, ..., 'z' = 25). This provides the same O(1) lookup time as a hash set but with slightly better constant factors due to simpler memory access patterns.

Algorithm

Create a boolean array of size 26, initialized to false.
For each character in allowed, mark the corresponding index as true.
Initialize res to the total number of words.
For each word in words:
- For each character in the word, check if the corresponding index in the boolean array is true.
- If any character maps to false, decrement res and break out of the inner loop.
Return res.

class Solution:
    def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
        allowedArr = [False] * 26
        for c in allowed:
            allowedArr[ord(c) - ord('a')] = True

        res = len(words)
        for w in words:
            for c in w:
                if not allowedArr[ord(c) - ord('a')]:
                    res -= 1
                    break

        return res

Time & Space Complexity

Time complexity: $O(n * l + m)$
Space complexity: $O(m)$

Where $n$ is the number of words, $m$ is the length of the string $allowed$ , and $l$ is the length of the longest word.

4. Bitmask

Intuition

We can compress the boolean array into a single 32-bit integer using bit manipulation. Each bit position represents whether a character is allowed (bit i represents the character 'a' + i). This approach uses constant space (just one integer) and leverages fast bitwise operations for lookups.

Algorithm

Initialize a bitmask integer to 0.
For each character in allowed, set the corresponding bit using OR operation: bit_mask |= (1 << (char - 'a')).
Initialize res to the total number of words.
For each word in words:
- For each character in the word, compute its bit position and check if that bit is set in the bitmask using AND operation.
- If the result is 0 (bit not set), decrement res and break out of the inner loop.
Return res.

class Solution:
    def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
        bit_mask = 0
        for c in allowed:
            bit = 1 << (ord(c) - ord('a'))
            bit_mask = bit_mask | bit

        res = len(words)
        for w in words:
            for c in w:
                bit = 1 << (ord(c) - ord('a'))
                if bit & bit_mask == 0:
                    res -= 1
                    break

        return res

Time & Space Complexity

Time complexity: $O(n * l + m)$
Space complexity: $O(1)$

Where $n$ is the number of words, $m$ is the length of the string $allowed$ , and $l$ is the length of the longest word.

Common Pitfalls

Forgetting to Break Early

When a word is found to be inconsistent, failing to break out of the inner loop wastes time checking remaining characters. This does not affect correctness but can significantly impact performance.

# Incorrect - continues checking after finding invalid character
for c in w:
    if c not in allowed:
        flag = False
        # Missing break!

# Correct - exits immediately when inconsistent
for c in w:
    if c not in allowed:
        flag = False
        break

Incorrect Bitmask Check

When using the bitmask approach, a common mistake is checking if the bit equals 1 instead of checking if it is non-zero. The bit position varies, so the result of the AND operation will be a power of 2, not necessarily 1.

# Incorrect - bit & mask could be 2, 4, 8, etc., not 1
if (bit & bit_mask) == 1:
    res -= 1

# Correct - check if the result is zero
if (bit & bit_mask) == 0:
    res -= 1