Problem Description

The "Maximum Number of Words You Can Type" problem asks you to determine how many words in a given text can be typed when certain keys on the keyboard are broken.

Specifically:

• You are given a string text consisting of words separated by single spaces.
• You are also given a string brokenLetters containing distinct lowercase English letters, each representing a broken key on the keyboard.
• Your task is to count how many words in text do not contain any letter from brokenLetters.

• Each word in text is non-empty and separated by exactly one space.
• All characters are lowercase English letters.
• You must not reuse or "fix" broken letters; if a word contains any broken letter, it cannot be typed.

Thought Process

Before jumping into code, let's consider how to solve the problem efficiently:

• A brute-force approach would be to check every letter of every word against every broken letter, but this could be slow if the input is large.
• We notice that for each word, we only need to check if any of its letters appear in brokenLetters.
• Comparing each letter of each word to the broken letters one by one would be slow if we had to search through a list each time.
• However, if we store the broken letters in a data structure that supports fast lookups (like a set), we can quickly check if a letter is broken.
• Thus, the main idea is: for each word, check if it has any letter in the set of broken letters. If it doesn't, increment our count.

Solution Approach

Let's break down the steps for an efficient solution:

1. Store Broken Letters: Place all characters from brokenLetters into a set. This allows O(1) lookup for each character.
2. Split Text into Words: Use the split function to divide text into a list/array of words.
3. Check Each Word: For each word, check if any of its letters are in the broken set.
   • If a word does not contain any broken letter, increment a counter.
   • If it contains at least one broken letter, skip it.
4. Return the Count: After checking all words, return the counter as the answer.

Example Walkthrough

Let's walk through an example step by step:
Input:

• text = "hello world leetcode"
• brokenLetters = "ad"

1. Convert brokenLetters to a set: {'a', 'd'}
2. Split text into words: ["hello", "world", "leetcode"]
3. For each word:
   • "hello": letters are h, e, l, l, o. None are broken. Count = 1
   • "world": letters are w, o, r, l, d. d is broken. Skip
   • "leetcode": letters are l, e, e, t, c, o, d, e. d is broken. Skip
4. Final count: 1

Time and Space Complexity

Brute-force approach:

• For each word (say n words), for each letter in the word (average length m), for each broken letter (length b): O(n * m * b)

• Building the broken-letter set: O(b)
• Splitting the text: O(L) where L is the total length of text
• For each word, check each letter: O(n * m) with O(1) lookup per letter
• Total: O(L + b) (since every character is checked once)
• Space: O(b) for the set, plus space for the split words

Summary

In summary, the problem is solved efficiently by:

• Using a set for fast checking of broken letters
• Splitting the text into words and checking each word for broken letters
• Counting words that do not contain any broken letter

Code Implementation

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

class Solution {
public:
    int canBeTypedWords(string text, string brokenLetters) {
        unordered_set<char> broken(brokenLetters.begin(), brokenLetters.end());
        int count = 0;
        istringstream iss(text);
        string word;
        while (iss >> word) {
            bool canType = true;
            for (char ch : word) {
                if (broken.count(ch)) {
                    canType = false;
                    break;
                }
            }
            if (canType) count++;
        }
        return count;
    }
};
      

class Solution {
    public int canBeTypedWords(String text, String brokenLetters) {
        Set<Character> broken = new HashSet<>();
        for (char ch : brokenLetters.toCharArray()) {
            broken.add(ch);
        }
        int count = 0;
        String[] words = text.split(" ");
        for (String word : words) {
            boolean canType = true;
            for (char ch : word.toCharArray()) {
                if (broken.contains(ch)) {
                    canType = false;
                    break;
                }
            }
            if (canType) count++;
        }
        return count;
    }
}
      

var canBeTypedWords = function(text, brokenLetters) {
    const broken = new Set(brokenLetters);
    let count = 0;
    const words = text.split(' ');
    for (const word of words) {
        let canType = true;
        for (const ch of word) {
            if (broken.has(ch)) {
                canType = false;
                break;
            }
        }
        if (canType) count++;
    }
    return count;
};