Problem Description

You are given a string allowed that contains distinct characters and an array of strings called words.

A string is considered consistent if every character in that string appears in the allowed string.

Your task is to count how many strings in the words array are consistent.

For example:

• If allowed = "ab" and words = ["ad", "bd", "aaab", "baa", "badab"]
• "aaab" is consistent because it only contains 'a' and 'b', which are both in allowed
• "baa" is consistent because it only contains 'a' and 'b', which are both in allowed
• "ad" is not consistent because it contains 'd', which is not in allowed
• "bd" is not consistent because it contains 'd', which is not in allowed
• "badab" is not consistent because it contains 'd', which is not in allowed
• The answer would be 2 (two consistent strings)

The solution uses a set to store all characters from allowed for O(1) lookup time. Then it iterates through each word in words, checking if all characters in that word exist in the set. The all() function returns True if every character c in word w is found in set s. The sum() function counts how many True values (consistent strings) there are.

Intuition

The key insight is that we need to check if each word is made up entirely of characters that exist in allowed. This is essentially a membership checking problem - for every character in a word, we need to verify it's a member of the allowed character set.

Since we'll be checking membership repeatedly (once for each character in each word), we want this operation to be as fast as possible. Converting allowed into a set gives us O(1) lookup time for each character check, rather than O(n) if we searched through the string each time.

The thought process flows naturally:

1. We need to validate each word individually - this suggests iterating through the words array
2. For each word, we need to ensure ALL its characters are valid - this suggests checking every character
3. A word is consistent only if every single character passes the test - if even one character isn't in allowed, the entire word fails

This "all or nothing" requirement makes the all() function a perfect fit - it returns True only when every character in the word exists in our allowed set. We can then use sum() to count the True values (Python treats True as 1 and False as 0), giving us the total count of consistent strings in a single, elegant line.

The beauty of this approach is its simplicity - we're essentially filtering and counting in one pass through the data, with optimal time complexity for the membership checks.

Solution Approach

The solution uses a Hash Table (implemented as a Python set) to efficiently check character membership.

Step-by-step implementation:

1. Convert allowed string to a set:

   s = set(allowed)

   This transformation takes O(m) time where m is the length of allowed, but gives us O(1) lookup time for each character check later.

2. Iterate through each word and validate:

   return sum(all(c in s for c in w) for w in words)

   Breaking this down:

   • for w in words: Iterate through each word in the array
   • for c in w: For each word, check every character
   • c in s: Test if character c exists in our set s (O(1) operation)
   • all(...): Returns True only if ALL characters in the word are found in the set
   • sum(...): Counts the number of True values (consistent strings)

Time Complexity Analysis:

• Creating the set: O(m) where m = length of allowed
• Checking all words: O(n × k) where n = number of words, k = average length of each word
• Total: O(m + n × k)

Space Complexity:

• O(m) for storing the set of allowed characters

The algorithm efficiently handles the validation by:

• Pre-processing the allowed characters into a set for fast lookups
• Using Python's built-in all() function to short-circuit - if any character isn't in the set, it immediately returns False without checking the remaining characters
• Leveraging sum() with a generator expression to count in a single pass without creating intermediate lists

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Given:

• allowed = "abc"
• words = ["a", "b", "cb", "abd", "dd"]

Step 1: Convert allowed string to a set

s = set("abc") = {'a', 'b', 'c'}

Step 2: Check each word for consistency

Let's trace through each word:

1. Word: "a"

   • Check: Is 'a' in {'a', 'b', 'c'}? → Yes ✓
   • All characters valid → Consistent (count = 1)

2. Word: "b"

   • Check: Is 'b' in {'a', 'b', 'c'}? → Yes ✓
   • All characters valid → Consistent (count = 2)

3. Word: "cb"

   • Check: Is 'c' in {'a', 'b', 'c'}? → Yes ✓
   • Check: Is 'b' in {'a', 'b', 'c'}? → Yes ✓
   • All characters valid → Consistent (count = 3)

4. Word: "abd"

   • Check: Is 'a' in {'a', 'b', 'c'}? → Yes ✓
   • Check: Is 'b' in {'a', 'b', 'c'}? → Yes ✓
   • Check: Is 'd' in {'a', 'b', 'c'}? → No ✗
   • Not all characters valid → Not Consistent (count = 3)

5. Word: "dd"

   • Check: Is 'd' in {'a', 'b', 'c'}? → No ✗
   • (Short-circuits here - no need to check the second 'd')
   • Not all characters valid → Not Consistent (count = 3)

Final Answer: 3

The code sum(all(c in s for c in w) for w in words) evaluates to:

• "a": all(['a' in s]) = True → 1
• "b": all(['b' in s]) = True → 1
• "cb": all(['c' in s, 'b' in s]) = True → 1
• "abd": all(['a' in s, 'b' in s, 'd' in s]) = False → 0
• "dd": all(['d' in s, 'd' in s]) = False → 0

Sum = 1 + 1 + 1 + 0 + 0 = 3

Solution Implementation

Time and Space Complexity

Time Complexity: O(m), where m is the total length of all strings in the words list.

The algorithm works as follows:

• Creating a set from allowed takes O(|allowed|) time
• For each word w in words, we check if all characters c in w are in the set s
• Checking if a character is in a set takes O(1) time on average
• The total number of character checks across all words equals the sum of lengths of all words, which is m
• Therefore, the overall time complexity is O(|allowed| + m), which simplifies to O(m) since typically m >> |allowed|

Space Complexity: O(C), where C is the size of the character set in allowed.

The space analysis:

• We create a set s from the allowed string, which stores at most C unique characters
• In this problem, since allowed contains only lowercase English letters, C ≤ 26
• The generator expression and sum() function use O(1) additional space
• Therefore, the space complexity is O(C)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Using String Instead of Set for Lookups

A frequent mistake is checking character membership directly in the allowed string rather than converting it to a set first.

Incorrect approach:

def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
    # Wrong: Using string for membership checks
    return sum(all(c in allowed for c in w) for w in words)

Why it's problematic:

• Checking c in allowed on a string has O(m) time complexity for each lookup
• With multiple words and characters, this becomes O(n × k × m) instead of O(n × k)
• For large allowed strings, this significantly impacts performance

Correct approach:

def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
    # Right: Convert to set first
    allowed_set = set(allowed)
    return sum(all(c in allowed_set for c in w) for w in words)

2. Not Handling Empty Strings or Edge Cases

While the problem likely guarantees non-empty inputs, defensive programming suggests checking edge cases.

Potential issue:

# Might fail with empty allowed string or None values
allowed_set = set(allowed)  # What if allowed is None or empty?

Robust solution:

def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
    if not allowed or not words:
        return 0 if not allowed else len([w for w in words if w == ""])
  
    allowed_set = set(allowed)
    return sum(all(c in allowed_set for c in w) for w in words)

3. Using Set Operations Incorrectly

Some attempt to use set operations but apply them incorrectly.

Common mistake:

def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
    allowed_set = set(allowed)
    count = 0
    for word in words:
        # Wrong: This checks if sets are equal, not if word chars are subset
        if set(word) == allowed_set:
            count += 1
    return count

Correct set-based approach:

def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
    allowed_set = set(allowed)
    count = 0
    for word in words:
        # Right: Check if word's characters are subset of allowed
        if set(word).issubset(allowed_set):
            count += 1
    return count

4. Misunderstanding the Problem Requirements

A critical misread is thinking we need to use ALL allowed characters, rather than ensuring words ONLY contain allowed characters.

Wrong interpretation:

# Incorrectly checking if word contains all allowed characters
if all(c in word for c in allowed):  # Wrong direction!

Correct interpretation:

# Correctly checking if all word characters are in allowed
if all(c in allowed_set for c in word):  # Right direction!