Maximum Number of Words You Can Type

Maximum Number of Words You Can Type

What is this problem about?

The Maximum Number of Words You Can Type coding problem gives you a text string (a sentence) and a brokenLetters string (containing all the characters that are broken on your keyboard). You need to count how many words in the text can be typed completely, meaning none of their characters appear in brokenLetters.

Why is this asked in interviews?

Quora, Microsoft, and Amazon use this as an easy problem to test fundamental string manipulation, set operations, and iteration skills. It's a good way to assess a candidate's ability to convert a problem into efficient data structure usage (like a hash set for brokenLetters).

Algorithmic pattern used

Hash Set + Iteration: The most efficient way to check if a word contains any broken letters is to put all brokenLetters into a hash set for O(1) average-case lookup. Then, iterate through each word in the text. For each word, iterate through its characters. If any character is found in the brokenLetters hash set, the word cannot be typed; move to the next word. If a word is fully traversed without finding any broken letters, increment a counter.

1. Create a broken_set (hash set) from brokenLetters for O(1) average-case lookups.
2. Initialize typable_words_count = 0.
3. Split the text into individual words (e.g., using space as a delimiter).
4. For each word in the words list: a. Set can_type_word = true. b. For each char in the word: i. If char is in broken_set: can_type_word = false. Break from this inner loop (no need to check further characters in this word). c. If can_type_word is true (after checking all its characters): typable_words_count++.
5. Return typable_words_count.

Example explanation

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

1. broken_set = {'a', 'd'}.

2. typable_words_count = 0.

3. Words: ["hello", "world"]

4. Word "hello":

   • 'h' not in broken_set.
   • 'e' not in broken_set.
   • 'l' not in broken_set.
   • 'l' not in broken_set.
   • 'o' not in broken_set.
   • All characters checked, can_type_word is true. typable_words_count = 1.

5. Word "world":

   • 'w' not in broken_set.
   • 'o' not in broken_set.
   • 'r' not in broken_set.
   • 'l' not in broken_set.
   • 'd' is in broken_set. can_type_word = false. Break.
   • can_type_word is false, so typable_words_count remains 1.

Result: 1.

Common mistakes candidates make

• Inefficient lookup: Iterating through brokenLetters for each character in each word results in O(L_text * L_word * L_broken) complexity, where L is length. Hash set reduces this to O(L_text * L_word + L_broken).
• Incorrect word splitting: Similar to the previous problem, ensure proper word splitting, especially for multiple spaces.
• Case sensitivity: Clarify if capitalization matters (e.g., if 'a' is broken, is 'A' also broken?). The problem typically implies case-insensitive or all lowercase.

Interview preparation tip

For the Hash Table String interview pattern, this problem is a good example of how to use hash sets for efficient membership testing. It's a common technique for optimizing problems that involve checking for forbidden characters or elements.