Maximum Number of Words You Can Type - Solution & Explanation
Problem Statement
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 <= 26textconsists of words separated by a single space without any leading or trailing spaces.- Each word only consists of lowercase English letters.
brokenLettersconsists of distinct lowercase English letters.
Approach Overview
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 1: Approach 1: Checking Each Word for Broken Letters
In this approach, we will iterate over each word in the text and check if any of its characters are in the brokenLetters string. If a word does not contain any broken letters, it will be considered typeable, and we increment our count. This approach leverages the distinct nature of broken letters, allowing us to efficiently check inclusion using a set data structure.
The C language solution uses the strtok function to split the input text into words. It checks each character of a word against the brokenLetters using strchr. If none of the broken letters are in the word, the word is counted as typeable.
Complexity
Time Complexity: O(n * m), where n is the number of characters in the text and m is the number of broken letters. Space Complexity: O(1), since we only maintain a few additional variables.
Approach 2: Approach 2: Set Intersection to Determine Typeable Words
This approach relies on using set operations to determine each word's typeability efficiently. By converting the text and broken letters into sets, we can directly determine if a word includes any broken letters using intersection operations.
Python's set capabilities allow us to efficiently determine if any of the broken letters appear in each word by using the intersection operator `&`. If the intersection is empty, the word can be typed.
Code
Python
JavaScript
Complexity
Time Complexity: O(n + m), where n is the total number of characters in the text, and m is the number of broken letters. Space Complexity: O(m) for storing broken letters as a set.
Approach 3: Array or Hash Table
We can use a hash table or an array s of length 26 to record all the broken letter keys.
Then, we traverse each word w in the string text, and if any letter c in w appears in s, it means that the word cannot be typed, and we do not need to add one to the answer. Otherwise, we need to add one to the answer.
After the traversal, we return the answer.
The time complexity is O(n), and the space complexity is O(|\Sigma|), where n is the length of the string text, and |\Sigma| is the size of the alphabet. In this problem, |\Sigma|=26.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Checking Each Word for Broken Letters | Time Complexity: O(n * m), where n is the number of characters in the text and m is the number of broken letters. Space Complexity: O(1), since we only maintain a few additional variables. |
| Approach 2: Set Intersection to Determine Typeable Words | Time Complexity: O(n + m), where n is the total number of characters in the text, and m is the number of broken letters. Space Complexity: O(m) for storing broken letters as a set. |
| Array or Hash Table | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Maximum Number of Words You Can Type | Simple Approach | Leetcode 1935 | codestorywithMIK • codestorywithMIK • 4,701 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Maximum Number of Words You Can Type easy or hard?
How to solve Maximum Number of Words You Can Type in O(n)?
Maximum Number of Words You Can Type Python or Java solution
What is the best approach for Maximum Number of Words You Can Type?
What data structure is used in Maximum Number of Words You Can Type?
What is the time complexity of Maximum Number of Words You Can Type?
Is Maximum Number of Words You Can Type asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Maximum Number of Words You Can Type with our built-in code editor and test cases.
Practice on FleetCode