LeetCode 1935 - Maximum Number of Words You Can Type

The problem is asking us to determine how many words in a given string can be fully typed on a malfunctioning keyboard. The keyboard has some broken letter keys that cannot be used.

leetcodeeasyhash-tablestring

LeetCode Problem 1935

Difficulty: 🟢 Easy
Topics: Hash Table, String

Solution

Problem Understanding

The problem is asking us to determine how many words in a given string can be fully typed on a malfunctioning keyboard. The keyboard has some broken letter keys that cannot be used. The input consists of a string text containing words separated by spaces, and a string brokenLetters containing the distinct letters that are broken. The output is a single integer representing the count of words that do not contain any broken letters and are therefore fully typeable.

The key constraints are that text can be up to 10,000 characters long, brokenLetters contains at most 26 characters (all distinct lowercase letters), and text contains only lowercase letters separated by single spaces with no leading or trailing spaces. This implies the solution must efficiently check each word against the broken letters without excessive repeated computation.

Edge cases include when brokenLetters is empty (all words are typeable), when every word contains at least one broken letter (output is 0), and when text consists of a single long word. The problem guarantees that words are separated by exactly one space and letters are lowercase, which simplifies parsing and comparison.

Approaches

A brute-force approach would iterate over every word in text and check each character against all broken letters. For every word, if any character is broken, the word is skipped; otherwise, it is counted. This works correctly but could be inefficient if text is very long, as checking membership in a string of broken letters is O(k) per character, leading to O(n*k) overall where n is the length of text and k is the length of brokenLetters.

The optimal approach uses a set to store brokenLetters for O(1) membership checks. Then we split text into words and, for each word, check if any of its characters are in the broken set. If none are broken, we increment the count. Using a set drastically reduces lookup time compared to a string or list, making the solution efficient and straightforward.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * k) O(1) Check each character of each word against string of broken letters
Optimal O(n + k) O(k) Convert broken letters to a set for O(1) lookups, check each word once

Algorithm Walkthrough

  1. Convert the string brokenLetters into a set called broken_set. This allows constant-time membership checks for any letter in O(1) time.
  2. Split the string text into individual words using the space character as a delimiter. This produces a list of words.
  3. Initialize a counter variable count to zero. This will store the number of words that can be typed fully.
  4. Iterate over each word in the list of words. For each word:

a. Check if any letter of the word exists in broken_set.

b. If a letter exists in the set, skip the word; otherwise, increment the count by one. 5. After iterating through all words, return the value of count.

Why it works: The algorithm guarantees correctness because it explicitly checks every letter of every word against all broken letters using an efficient set lookup. By incrementing the counter only when a word has no broken letters, the returned count accurately represents all typeable words.

Python Solution

class Solution:
    def canBeTypedWords(self, text: str, brokenLetters: str) -> int:
        broken_set = set(brokenLetters)
        count = 0
        
        for word in text.split():
            if all(char not in broken_set for char in word):
                count += 1
        
        return count

The implementation first converts brokenLetters into a set for fast membership checking. The text is split into words using split(). For each word, a generator expression checks that no character exists in broken_set. If the word passes this check, count is incremented. Finally, count is returned.

Go Solution

func canBeTypedWords(text string, brokenLetters string) int {
    brokenSet := make(map[rune]bool)
    for _, ch := range brokenLetters {
        brokenSet[ch] = true
    }

    words := strings.Fields(text)
    count := 0

    for _, word := range words {
        canType := true
        for _, ch := range word {
            if brokenSet[ch] {
                canType = false
                break
            }
        }
        if canType {
            count++
        }
    }

    return count
}

In Go, brokenLetters is converted into a map for O(1) lookups. strings.Fields is used to split the text into words safely. A boolean canType tracks whether the current word can be typed. The word is iterated rune by rune to handle all letters correctly. If any letter is broken, the word is skipped.

Worked Examples

Example 1:

text = "hello world", brokenLetters = "ad"

Word Letters in broken set? Count
hello no 1
world yes ('d') 1

Output: 1

Example 2:

text = "leet code", brokenLetters = "lt"

Word Letters in broken set? Count
leet yes ('l', 't') 0
code no 1

Output: 1

Example 3:

text = "leet code", brokenLetters = "e"

Word Letters in broken set? Count
leet yes ('e') 0
code yes ('e') 0

Output: 0

Complexity Analysis

Measure Complexity Explanation
Time O(n + k) O(k) for creating the broken letters set and O(n) to iterate over all characters in text
Space O(k) O(k) for storing broken letters in a set

The algorithm is linear with respect to the length of text and the number of broken letters. Using a set for broken letters ensures fast lookups and minimal overhead.

Test Cases

# test cases
assert Solution().canBeTypedWords("hello world", "ad") == 1  # basic test
assert Solution().canBeTypedWords("leet code", "lt") == 1   # multiple broken letters
assert Solution().canBeTypedWords("leet code", "e") == 0    # all words blocked
assert Solution().canBeTypedWords("a b c", "") == 3         # no broken letters
assert Solution().canBeTypedWords("a b c", "abc") == 0      # all letters broken
assert Solution().canBeTypedWords("aaa bbb ccc", "a") == 2  # some words blocked
assert Solution().canBeTypedWords("singleword", "s") == 0   # single word blocked
assert Solution().canBeTypedWords("singleword", "") == 1    # single word not blocked
Test Why
"hello world", "ad" basic functionality
"leet code", "lt" multiple broken letters in a word
"leet code", "e" broken letter appears in every word
"a b c", "" no broken letters, all words typeable
"a b c", "abc" all letters broken, none typeable
"aaa bbb ccc", "a" partial blocking of words
"singleword", "s" edge case with single word blocked
"singleword", "" edge case with single word allowed

Edge Cases

One important edge case is when brokenLetters is empty. This could cause a naive implementation that assumes the set is non-empty to fail. Our solution handles this correctly because the set will simply be empty, and all char not in broken_set checks will pass.

Another edge case is when every word contains at least one broken letter. Without careful handling, a loop may accidentally count a blocked word. Our implementation ensures that a word is only counted if no letters appear in broken_set.

A third edge case is when text consists of a single very long word. Some solutions that split by spaces or iterate inefficiently could have performance issues. Our algorithm handles it correctly because it processes characters in a single pass and does not rely on nested loops over words unnecessarily.