Watch 10 video solutions for Maximum Number of Words You Can Type, a easy level problem involving Hash Table, String. This walkthrough by codestorywithMIK has 4,603 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There is a malfunctioning keyboard where some letter keys do not work. All other keys on the keyboard work properly.
Given a string text of words separated by a single space (no leading or trailing spaces) and a string brokenLetters of all distinct letter keys that are broken, return the number of words in text you can fully type using this keyboard.
Example 1:
Input: text = "hello world", brokenLetters = "ad" Output: 1 Explanation: We cannot type "world" because the 'd' key is broken.
Example 2:
Input: text = "leet code", brokenLetters = "lt" Output: 1 Explanation: We cannot type "leet" because the 'l' and 't' keys are broken.
Example 3:
Input: text = "leet code", brokenLetters = "e" Output: 0 Explanation: We cannot type either word because the 'e' key is broken.
Constraints:
1 <= text.length <= 1040 <= brokenLetters.length <= 26text consists of words separated by a single space without any leading or trailing spaces.brokenLetters consists of distinct lowercase English letters.Problem Overview: You are given a sentence and a string representing broken keyboard letters. A word can be typed only if none of its characters appear in the broken set. The task is to count how many words in the sentence are fully typeable.
Approach 1: Checking Each Word for Broken Letters (O(n * m) time, O(b) space)
Split the sentence into individual words, then examine each word character by character. Store the broken letters in a hash set so every lookup runs in constant time. For every word, iterate through its characters and check whether any character exists in the broken set. If you encounter a broken letter, mark the word as invalid and move to the next one. This approach is straightforward and efficient because membership checks in a hash table are O(1). The overall runtime becomes O(n * m), where n is the number of words and m is the average word length.
Approach 2: Set Intersection to Determine Typeable Words (O(n * m) time, O(m + b) space)
Instead of scanning characters manually, convert each word into a character set and compute the intersection with the broken letters set. If the intersection is empty, the word is typeable. This approach relies heavily on built-in set operations in languages like Python or JavaScript, which are implemented efficiently in native code. The complexity remains O(n * m) because each word still requires processing all its characters, but the implementation is often shorter and easier to read.
Both methods rely on fast membership checks using a hash table or set structure. Since the input is primarily text processing, efficient iteration over characters in a string is the main operation. The difference is mostly stylistic: explicit iteration versus set operations.
Recommended for interviews: Approach 1 is usually preferred. It demonstrates clear control over iteration and hash lookups, which interviewers expect when testing basic string processing and set membership. Approach 2 is concise and elegant but relies more on language-specific conveniences. Showing the direct character-checking solution proves you understand the underlying logic rather than just using built-in set operations.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Checking Each Word for Broken Letters | O(n * m) | O(b) | General case. Clear logic using hash set lookups and character iteration. |
| Set Intersection Between Word and Broken Letters | O(n * m) | O(m + b) | When using languages with efficient built-in set operations like Python or JavaScript. |