Problem Description

You have a keyboard where some letter keys are broken and don't work, while all other keys function normally.

Given two inputs:

• text: a string containing words separated by single spaces (with no leading or trailing spaces)
• brokenLetters: a string containing all the distinct letters that are broken on the keyboard

Your task is to count how many complete words from text can be typed using this malfunctioning keyboard. A word can only be typed if none of its letters appear in the broken letters list.

For example, if brokenLetters = "ab" and text = "hello world", you can type both words since neither contains 'a' or 'b', so the answer would be 2. But if text = "leet code" with the same broken letters, you could only type "leet" (not "code" which contains 'a'), so the answer would be 1.

The solution uses a set to store broken letters for O(1) lookup time, then checks each word in the text. For each word, it verifies that none of its characters appear in the broken letters set. The all() function returns True only if every character in the word is not broken, and the sum() counts how many words satisfy this condition.

Intuition

The key insight is that we need to check each word independently to see if it can be typed. A word is "typeable" only if it doesn't contain any broken letters.

Think of it like a filter problem: we're filtering out words that contain forbidden characters. The natural approach is to:

1. First, create a quick way to check if a letter is broken. Using a set for brokenLetters gives us O(1) lookup time for each character check.

2. For each word, we need to verify that ALL its characters are typeable (not broken). This is a perfect use case for the all() function - it returns True only when every character passes our test.

3. The expression c not in s for c in w generates a boolean for each character in word w, checking if that character is NOT in the broken set.

4. Since all() returns a boolean (True if the word is typeable, False otherwise), we can directly sum these boolean values. In Python, True counts as 1 and False as 0, so sum() gives us the total count of typeable words.

The elegance of this solution comes from recognizing that counting valid words is equivalent to summing boolean results - each word either contributes 1 (if typeable) or 0 (if not) to our final count. This transforms the problem from explicit counting with conditionals to a simple summation of boolean expressions.

Solution Approach

We implement the solution using a hash table (set) to store broken letters and iterate through each word to check if it can be typed.

Step 1: Create a Set for Broken Letters

s = set(brokenLetters)

We convert the brokenLetters string into a set s. This gives us O(1) time complexity for checking if a character is broken, which is more efficient than repeatedly searching through the original string.

Step 2: Process Each Word

text.split()

We split the input text by spaces to get individual words. Since the problem guarantees no leading or trailing spaces and single spaces between words, split() without arguments works perfectly.

Step 3: Check Each Word for Broken Letters

all(c not in s for c in w)

For each word w, we use a generator expression (c not in s for c in w) to check every character c in the word. This generates a sequence of boolean values - True if the character is not broken, False if it is broken.

The all() function returns:

• True only if ALL characters in the word are not in the broken set (meaning the word can be typed)
• False if ANY character is broken (meaning the word cannot be typed)

Step 4: Count Valid Words

sum(all(c not in s for c in w) for w in text.split())

We use sum() to count how many words can be typed. Since all() returns a boolean value for each word (True = 1, False = 0), summing these values gives us the total count of typeable words.

Time Complexity: O(n) where n is the total number of characters in text, as we visit each character once.

Space Complexity: O(m) where m is the number of broken letters, for storing the set.

Example Walkthrough

Let's walk through the solution with a concrete example to see how it works step by step.

Given:

• text = "hello world leet code"
• brokenLetters = "aeo"

Step 1: Create the broken letters set

s = set("aeo")  # s = {'a', 'e', 'o'}

Step 2: Split text into words

words = text.split()  # ["hello", "world", "leet", "code"]

Step 3: Check each word

For word "hello":

• Check 'h': not in {'a', 'e', 'o'} → True
• Check 'e': in {'a', 'e', 'o'} → False
• Check 'l': not in {'a', 'e', 'o'} → True
• Check 'l': not in {'a', 'e', 'o'} → True
• Check 'o': in {'a', 'e', 'o'} → False
• all([True, False, True, True, False]) → False (can't type "hello")

For word "world":

• Check 'w': not in {'a', 'e', 'o'} → True
• Check 'o': in {'a', 'e', 'o'} → False
• Check 'r': not in {'a', 'e', 'o'} → True
• Check 'l': not in {'a', 'e', 'o'} → True
• Check 'd': not in {'a', 'e', 'o'} → True
• all([True, False, True, True, True]) → False (can't type "world")

For word "leet":

• Check 'l': not in {'a', 'e', 'o'} → True
• Check 'e': in {'a', 'e', 'o'} → False
• Check 'e': in {'a', 'e', 'o'} → False
• Check 't': not in {'a', 'e', 'o'} → True
• all([True, False, False, True]) → False (can't type "leet")

For word "code":

• Check 'c': not in {'a', 'e', 'o'} → True
• Check 'o': in {'a', 'e', 'o'} → False
• Check 'd': not in {'a', 'e', 'o'} → True
• Check 'e': in {'a', 'e', 'o'} → False
• all([True, False, True, False]) → False (can't type "code")

Step 4: Sum the results

sum([False, False, False, False])  # 0 + 0 + 0 + 0 = 0

Result: 0 words can be typed

Let's try another example where some words CAN be typed:

• text = "cat dog fish"
• brokenLetters = "e"
• Words check: "cat" (✓), "dog" (✓), "fish" (✓)
• All three words contain no 'e', so the answer is 3

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string text. This is because:

• Converting brokenLetters to a set takes O(|brokenLetters|) time, which is at most O(26) = O(1) since there are only 26 lowercase English letters
• text.split() iterates through the entire string once, taking O(n) time
• For each word w in the split result, we check each character c against the set s, which takes O(|w|) time per word
• The total time for checking all characters across all words is O(n) since we examine each character in text at most once (excluding spaces)
• Set membership testing (c not in s) is O(1) on average

The space complexity is O(|Σ|), where |Σ| is the size of the alphabet. In this problem, |Σ| = 26. This is because:

• The set s stores at most 26 unique characters (all lowercase English letters), requiring O(26) = O(|Σ|) space
• text.split() creates a list of words, which in worst case could be O(n) space, but since we're using a generator expression with sum() and all(), the words are processed one at a time without storing the entire list
• The generator expression and all() function use O(1) additional space

Therefore, the dominant space factor is the set storage, giving us O(|Σ|) space complexity.

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

Common Pitfalls

1. Not Handling Empty brokenLetters String

A common mistake is not considering the case when brokenLetters is an empty string. When creating a set from an empty string, it results in an empty set, which is actually correct behavior - no letters are broken, so all words can be typed. However, some might try to add unnecessary special case handling.

Incorrect approach:

if not brokenLetters:
    return len(text.split())  # Unnecessary special case
broken_letters_set = set(brokenLetters)

Correct approach:

broken_letters_set = set(brokenLetters)  # Works correctly even when empty

2. Using String Search Instead of Set Lookup

Some might use in brokenLetters directly instead of converting to a set first. This leads to worse time complexity.

Inefficient approach:

for char in word:
    if char in brokenLetters:  # O(k) lookup where k = len(brokenLetters)
        can_type_word = False

Efficient approach:

broken_letters_set = set(brokenLetters)
for char in word:
    if char in broken_letters_set:  # O(1) lookup
        can_type_word = False

3. Incorrect Use of any() Instead of all()

A subtle logical error occurs when mixing up any() and all(). Some might write:

Incorrect:

sum(any(c not in s for c in w) for w in text.split())

This counts words that have AT LEAST ONE typeable character, not words where ALL characters are typeable.

Correct:

sum(all(c not in s for c in w) for w in text.split())

4. Not Breaking Early in Loop

When checking if a word can be typed, once we find a broken letter, we should immediately stop checking that word.

Inefficient approach:

for word in words:
    broken_count = 0
    for char in word:
        if char in broken_letters_set:
            broken_count += 1  # Continues checking even after finding broken letter
    if broken_count == 0:
        typeable_count += 1

Efficient approach:

for word in words:
    can_type_word = True
    for char in word:
        if char in broken_letters_set:
            can_type_word = False
            break  # Stop checking once we find a broken letter

5. Case Sensitivity Assumptions

The problem doesn't specify case handling. If the keyboard has a broken 'A', can we type 'a'? Without clarification, the solution treats uppercase and lowercase as different characters. If case-insensitive matching is needed:

Case-sensitive (default):

broken_letters_set = set(brokenLetters)

Case-insensitive (if required):

broken_letters_set = set(brokenLetters.lower())
# And check: if char.lower() in broken_letters_set