#1684

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Count the Number of Consistent Strings

Count the number of strings fully composed of allowed characters using array scanning and hash lookup for efficiency.

array hash table string bit manipulation counting

Problem Statement

You are given a string allowed consisting of distinct lowercase characters and an array of strings words. A string is consistent if every character in the string appears in allowed. Return the total number of consistent strings found in words.

For example, given allowed = "ab" and words = ["ad","bd","aaab","baa","badab"], only "aaab" and "baa" are consistent because they only use characters 'a' and 'b'. Count these consistent strings and return the total.

Examples

Example 1

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

Output: 2

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

All strings are consistent.

Example 3

Input: allowed = "cad", words = ["cc","acd","b","ba","bac","bad","ac","d"]

Output: 4

Strings "cc", "acd", "ac", and "d" are consistent.

Constraints

1 <= words.length <= 104
1 <= allowed.length <= 26
1 <= words[i].length <= 10
The characters in allowed are distinct.
words[i] and allowed contain only lowercase English letters.

Solution Approach

Hash Set Lookup

Store all characters of allowed in a hash set. For each word, check every character against the set. If a character is missing, mark the word as inconsistent and skip counting it.

Bit Manipulation Optimization

Convert allowed characters into a bitmask where each bit represents a character. For each word, compute its bitmask and check if it fits entirely within the allowed bitmask. This provides faster membership checks for larger datasets.

Counting Consistent Strings

Iterate through words, using either hash set or bitmask checks. Increment a counter only for words where all characters are allowed. Return the counter as the total number of consistent strings.

Complexity Analysis

Metric	Value
Time	O(m + n \cdot k)
Space	O(1)

Time complexity is O(m + n * k), where m is the length of allowed, n is the number of words, and k is the average word length, because each character is checked once. Space complexity is O(1) because the hash set or bitmask uses a fixed size of at most 26 bits for lowercase letters.

What Interviewers Usually Probe

Expect recognition of the array scanning plus hash lookup pattern.
Look for discussion on avoiding nested loops by using set or bitmap membership checks.
Check if candidate handles edge cases like empty words or full alphabet allowed strings.

Common Pitfalls or Variants

Common pitfalls

Using nested loops without a hash set leads to O(n * k * m) complexity and TLE.
Forgetting that allowed contains only distinct characters, so duplicates in allowed are irrelevant.
Failing to handle words with characters outside 'a'-'z' could miscount consistent strings.

Follow-up variants

Return the list of consistent strings instead of the count.
Allow repeated characters in allowed and verify consistency without extra preprocessing.
Count strings consistent with multiple allowed sets and compare results.

FAQ

What is the main pattern used in Count the Number of Consistent Strings?

The problem uses array scanning plus hash lookup, allowing efficient checks for character consistency in each word.

Can bit manipulation replace hash sets for allowed character checks?

Yes, converting allowed characters to a bitmask enables constant-time membership checks and is more memory-efficient for small alphabets.

How do you handle empty words or an empty allowed string?

Empty words are always consistent, while an empty allowed string results in zero consistent strings since no characters are allowed.

What causes time limit exceeded errors in this problem?

Using nested loops to check each character against allowed without a hash set or bitmap can increase runtime significantly.

Is it necessary to pre-process allowed characters?

Yes, storing allowed characters in a hash set or bitmask ensures each character check is O(1) and avoids repeated linear scans.

terminal

Solution

Solution 1: Hash Table or Array

A straightforward approach is to use a hash table or array $s$ to record the characters in `allowed`. Then iterate over the `words` array, for each string $w$, determine whether it is composed of characters in `allowed`. If so, increment the answer.

1

2

3

4

class Solution:
    def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
        s = set(allowed)
        return sum(all(c in s for c in w) for w in words)

Solution 2: Bit Manipulation

We can also use a single integer to represent the occurrence of characters in each string. In this integer, each bit in the binary representation indicates whether a character appears.

1

2

3

4

class Solution:
    def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
        s = set(allowed)
        return sum(all(c in s for c in w) for w in words)

Continue Practicing

#1994 the number of good subsets #1366 rank teams by votes #2131 longest palindrome by concatenating two letter words