LeetCode 1684 - Count the Number of Consistent Strings

Difficulty: 🟢 Easy
Topics: Array, Hash Table, String, Bit Manipulation, Counting

Solution

Problem Understanding

This problem asks us to determine how many strings in the words array are consistent with a given set of allowed characters.

You are given two inputs:

allowed, a string containing distinct lowercase English letters.
words, an array of lowercase strings.

A word is considered consistent if every character in that word exists inside allowed. If even one character is not present in allowed, the word is inconsistent and should not be counted.

In simpler terms, we can think of allowed as a whitelist of valid characters. Every word in words must be checked character by character to ensure it only contains characters from this whitelist.

For example, if:

allowed = "ab"

Then valid words may only contain 'a' and 'b'.

"aaab" is valid because every letter is either 'a' or 'b'
"baa" is valid for the same reason
"ad" is invalid because 'd' is not allowed

The expected output is a single integer representing the total number of consistent strings.

Understanding the Constraints

The constraints provide useful insight into how efficient our solution needs to be:

1 <= words.length <= 10^4
1 <= allowed.length <= 26
1 <= words[i].length <= 10

The most important observation is that allowed has at most 26 characters, because it only contains lowercase English letters. This means we can efficiently store allowed characters in a structure optimized for fast membership lookup.

The total number of characters across all words is also relatively small:

10^4 words × 10 characters = at most 100,000 characters

This tells us an O(total_characters) solution is perfectly acceptable.

Important Edge Cases

Several edge cases are worth identifying early.

A word with a single invalid character should immediately be rejected. For example:

allowed = "abc"
word = "abx"

The presence of 'x' alone makes the word inconsistent.

The allowed string could contain only one character:

allowed = "a"
words = ["a", "aa", "aaa", "ab"]

Only words made entirely of 'a' are valid.

All words may already be consistent:

allowed = "abc"
words = ["a", "ab", "abc"]

In this case, the result equals the number of words.

Conversely, none of the words may be consistent:

allowed = "a"
words = ["b", "bc", "xyz"]

The result would be 0.

The problem guarantees several helpful conditions:

allowed contains distinct characters, so we do not need to handle duplicates.
All inputs contain only lowercase English letters, which makes character checking straightforward.
Every word has at least one character.

Approaches

Brute Force Approach

The most straightforward solution is to repeatedly search the allowed string for every character in every word.

For each word:

Iterate through every character.
Check whether that character exists inside allowed.
If any character is missing, reject the word.
Otherwise, count it as consistent.

Since allowed is a string, checking membership requires scanning it linearly.

For example:

allowed = "abc"
word = "ac"

To verify 'a', we scan "abc".

To verify 'c', we scan "abc" again.

This works correctly because every character is explicitly validated. However, repeatedly scanning allowed becomes inefficient when performed many times.

Key Insight for an Optimal Solution

The key observation is that we repeatedly ask the same question:

"Is this character allowed?"

Instead of scanning the allowed string every time, we should preprocess it into a data structure that supports constant-time membership checks.

A hash set is ideal for this.

We convert:

allowed = "abc"

into:

{'a', 'b', 'c'}

Now checking whether 'a' or 'c' is allowed becomes an average O(1) operation.

Then:

Build a set of allowed characters.
Iterate through each word.
Verify every character exists in the set.
Count valid words.

Since each character is checked only once, this becomes linear in the total number of characters.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(W × L × A)	O(1)	Scan `allowed` for every character, where `W` is number of words, `L` is average word length, `A` is length of `allowed`
Optimal	O(W × L)	O(A)	Use a hash set for constant-time character lookup

Where:

W = number of words
L = average word length
A = length of allowed

Since A ≤ 26, the extra memory is very small.

Algorithm Walkthrough

Step-by-Step Process

Convert allowed into a hash set

We place every character from allowed into a set so membership checks become fast.

Example:

allowed = "cad"

becomes:

{'c', 'a', 'd'}

Initialize a counter

We maintain a variable called consistent_count to track how many words are valid.

Initially:

consistent_count = 0

Iterate through every word

For each word in words, we test whether all characters are allowed. 4. Check each character in the word

Iterate through the characters of the current word.

If any character does not exist in the allowed set:

mark the word as inconsistent
stop checking that word immediately

This early stopping avoids unnecessary work. 5. Count valid words

If we finish checking a word without finding an invalid character, increment the counter. 6. Return the final count

After processing all words, return the total number of consistent strings.

Why it works

The algorithm works because every word is validated against the exact definition of consistency.

A word is consistent if and only if every character belongs to allowed. The hash set stores exactly the allowed characters, so checking membership directly verifies this condition.

The invariant is:

A word is counted only if every character passes the membership test.

Since every word is examined and invalid words are excluded immediately, the final count is guaranteed to be correct.

Python Solution

from typing import List

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

        for word in words:
            is_consistent = True

            for char in word:
                if char not in allowed_chars:
                    is_consistent = False
                    break

            if is_consistent:
                consistent_count += 1

        return consistent_count

The implementation begins by converting allowed into a set called allowed_chars. This preprocessing step enables constant-time membership checking.

We then initialize consistent_count, which stores the number of valid words found so far.

For each word, we assume it is valid by setting is_consistent = True.

We iterate through every character in the word. If we encounter a character that does not exist in allowed_chars, the word becomes invalid. We set is_consistent to False and immediately stop processing the word using break.

This early termination improves efficiency because there is no reason to continue checking a word that is already invalid.

After processing the word, if is_consistent is still True, we increment the counter.

Finally, we return the total count.

Go Solution

func countConsistentStrings(allowed string, words []string) int {
	allowedChars := make(map[rune]bool)

	for _, ch := range allowed {
		allowedChars[ch] = true
	}

	consistentCount := 0

	for _, word := range words {
		isConsistent := true

		for _, ch := range word {
			if !allowedChars[ch] {
				isConsistent = false
				break
			}
		}

		if isConsistent {
			consistentCount++
		}
	}

	return consistentCount
}

The Go implementation follows the same algorithmic structure as the Python version.

Instead of a Python set, Go uses a map[rune]bool to simulate constant-time membership checking.

We iterate over allowed and mark every character as true in the map.

For each word, we verify whether every character exists in the map. If an invalid character appears, we stop checking immediately.

Since the input contains only lowercase English letters, integer overflow is not a concern. Go slices naturally handle empty and non-empty inputs, and the constraints guarantee at least one word.

Worked Examples

Example 1

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

Allowed set:

{'a', 'b'}

Word	Character Check	Consistent?	Count
`"ad"`	`a` , `d`	No	0
`"bd"`	`b` , `d`	No	0
`"aaab"`	`a` , `a` , `a` , `b`	Yes	1
`"baa"`	`b` , `a` , `a`	Yes	2
`"badab"`	`b` , `a` , `d`	No	2

Final answer:

Example 2

allowed = "abc"
words = ["a","b","c","ab","ac","bc","abc"]

Allowed set:

{'a', 'b', 'c'}

Word	Character Check	Consistent?	Count
`"a"`	`a`	Yes	1
`"b"`	`b`	Yes	2
`"c"`	`c`	Yes	3
`"ab"`	`a` , `b`	Yes	4
`"ac"`	`a` , `c`	Yes	5
`"bc"`	`b` , `c`	Yes	6
`"abc"`	`a` , `b` , `c`	Yes	7

Final answer:

Example 3

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

Allowed set:

{'c', 'a', 'd'}

Word	Character Check	Consistent?	Count
`"cc"`	`c` , `c`	Yes	1
`"acd"`	`a` , `c` , `d`	Yes	2
`"b"`	`b`	No	2
`"ba"`	`b`	No	2
`"bac"`	`b`	No	2
`"bad"`	`b`	No	2
`"ac"`	`a` , `c`	Yes	3
`"d"`	`d`	Yes	4

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(W × L)	Each character across all words is checked once
Space	O(A)	The hash set stores characters from `allowed`

Here, W represents the number of words, L represents the average word length, and A represents the size of allowed.

Although the theoretical space complexity is O(A), in practice A ≤ 26, meaning the extra memory usage is effectively constant.

The runtime is linear because every character in every word is processed at most once, and set lookups are constant time on average.

Test Cases

class Solution:
    def countConsistentStrings(self, allowed, words):
        allowed_chars = set(allowed)
        count = 0

        for word in words:
            if all(char in allowed_chars for char in word):
                count += 1

        return count

solution = Solution()

assert solution.countConsistentStrings(
    "ab",
    ["ad", "bd", "aaab", "baa", "badab"]
) == 2  # Example 1

assert solution.countConsistentStrings(
    "abc",
    ["a", "b", "c", "ab", "ac", "bc", "abc"]
) == 7  # Example 2

assert solution.countConsistentStrings(
    "cad",
    ["cc", "acd", "b", "ba", "bac", "bad", "ac", "d"]
) == 4  # Example 3

assert solution.countConsistentStrings(
    "a",
    ["a", "aa", "aaa"]
) == 3  # Single allowed character, all valid

assert solution.countConsistentStrings(
    "a",
    ["b", "bb", "ab"]
) == 0  # No consistent words

assert solution.countConsistentStrings(
    "abcdefghijklmnopqrstuvwxyz",
    ["hello", "world", "leetcode"]
) == 3  # All lowercase letters allowed

assert solution.countConsistentStrings(
    "abc",
    ["x"]
) == 0  # Single invalid word

assert solution.countConsistentStrings(
    "abc",
    ["a"]
) == 1  # Single valid word

assert solution.countConsistentStrings(
    "abc",
    ["abx", "aby", "abz"]
) == 0  # Invalid character appears late

assert solution.countConsistentStrings(
    "xyz",
    ["x", "xx", "xy", "zzz"]
) == 4  # Repeated valid characters

Test	Why
Example 1	Validates mixed valid and invalid words
Example 2	Ensures all words can be counted
Example 3	Tests mixed outcomes with varied word lengths
Single allowed character	Verifies minimal `allowed` size
No consistent words	Ensures zero count is handled correctly
Full alphabet allowed	Confirms all lowercase words become valid
Single invalid word	Tests immediate rejection
Single valid word	Verifies smallest valid case
Invalid character late in word	Confirms checking continues until failure
Repeated valid characters	Ensures repeated letters work correctly

Edge Cases

Only One Allowed Character

A common source of bugs is when allowed contains only one character.

Example:

allowed = "a"
words = ["a", "aa", "aaa", "ab"]

A naive implementation might incorrectly assume uniqueness matters inside words. However, repeated characters are completely valid as long as they belong to allowed.

The implementation handles this correctly because every character is checked independently, and repeated membership checks still succeed.

Words With an Invalid Character Near the End

Consider:

allowed = "abc"
word = "abx"

A buggy implementation might accidentally stop too early or incorrectly mark the word valid after checking only a prefix.

Our implementation examines characters sequentially and rejects the word immediately upon finding 'x'. This guarantees correctness regardless of where the invalid character appears.

No Valid Words

Example:

allowed = "a"
words = ["b", "bb", "bc"]

Some implementations may accidentally initialize the count incorrectly or increment too early.

Our approach increments the counter only after confirming every character in the word is valid. Therefore, if no word passes validation, the method correctly returns 0.