Count the Number of Consistent Strings

How it works

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.

Steps

1. Initialize a bitmask integer to 0.
2. For each character in allowed, set the corresponding bit using OR operation: bit_mask |= (1 << (char - 'a')).
3. Initialize res to the total number of words.
4. 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.
5. Return res.

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.

Things to watch for

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

from typing import List

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

class Solution {
public:
    int countConsistentStrings(string allowed, vector<string>& words) {
        int bitMask = 0;
        for (char c : allowed) {
            bitMask |= (1 << (c - 'a'));
        }

        int res = words.size();
        for (const string& w : words) {
            for (char c : w) {
                int bit = 1 << (c - 'a');
                if ((bit & bitMask) == 0) {
                    res--;
                    break;
                }
            }
        }

        return res;
    }
};