Maximum Number of Words You Can Type
EasyPrompt
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.
Approaches
4 approaches with complexity analysis and trade-offs.
This approach directly translates the problem statement into code. It iterates through each word and, for every character in that word, it performs a linear scan through the brokenLetters string to see if there's a match. While straightforward, this method is computationally expensive.
Algorithm
- Split the
textstring into an array ofwords. - Initialize a counter
countto zero. - Iterate through each
wordin thewordsarray. - For each
word, set a flagcanTypetotrue. - Start a nested loop to iterate through each character
cof the currentword. - Inside this, start another nested loop to iterate through each character
binbrokenLetters. - If
cis equal tob, it means the word contains a broken letter. SetcanTypetofalseand break from the inner loops for this word. - If the loop for a word completes and
canTypeis stilltrue, incrementcount. - Return
countafter checking all words.
Walkthrough
The core idea is to check every character of every word against every single broken letter.
We begin by splitting the input text into an array of individual words. We then loop through this array. For each word, we assume it's typeable until proven otherwise. We do this by iterating through its characters. For each character, we perform another iteration through all the brokenLetters. If a match is found, we immediately know the word is not typeable, so we mark it as such and stop checking this particular word, moving on to the next one. If we manage to check all characters of a word without finding any broken letters, we increment our counter of typeable words.
public int canBeTypedWords(String text, String brokenLetters) { String[] words = text.split(" "); int count = 0; for (String word : words) { boolean canType = true; for (char c : word.toCharArray()) { // Inefficiently check against brokenLetters string if (brokenLetters.indexOf(c) != -1) { canType = false; break; } } if (canType) { count++; } } return count;}Complexity
Time
O(N * M), where N is the length of `text` and M is the length of `brokenLetters`. For each character in `text`, we might perform a search through `brokenLetters`, leading to a multiplicative complexity.
Space
O(N), where N is the length of the `text`. This is because splitting the string creates a new array of words which, in the worst case, can have a total size proportional to the original string.
Trade-offs
Pros
Very simple to conceptualize and implement.
Requires minimal auxiliary data structures.
Cons
Highly inefficient due to the triple nested loop structure (iterating words, characters in a word, and characters in brokenLetters).
The time complexity is poor, making it unsuitable for large inputs.
This approach improves upon the brute-force method by optimizing the lookup of broken letters. By storing the brokenLetters in a HashSet, we can check if a character is broken in constant average time, O(1), instead of linear time. This significantly reduces the overall time complexity.
Algorithm
- Create a
HashSet<Character>and populate it with all characters from thebrokenLettersstring. - Split the
textinto an array ofwords. - Initialize a counter
countto zero. - Iterate through each
wordin thewordsarray. - For each
word, assume it is typeable by setting a flagcanTypetotrue. - Iterate through the characters
cof the currentword. - For each character
c, check if it is present in theHashSet. This is an O(1) average time operation. - If
cis in the set, setcanTypetofalseand break the inner loop. - If the word's loop finishes and
canTypeis stilltrue, incrementcount. - Return
count.
Walkthrough
The main bottleneck in the brute-force approach is the repeated scanning of the brokenLetters string. We can eliminate this by pre-processing brokenLetters into a more efficient data structure. A HashSet is ideal for this, as it provides average O(1) time complexity for containment checks (contains() method).
First, we iterate through brokenLetters and add each character to a HashSet. Then, we proceed as before: split text into words and iterate through them. For each character of a word, we now use the HashSet's contains() method to check if it's a broken letter. This check is much faster. If a broken letter is found, we stop processing the current word and move to the next. If a word is traversed completely without any hits from the HashSet, it's deemed typeable, and we increment our count.
import java.util.HashSet;import java.util.Set; public int canBeTypedWords(String text, String brokenLetters) { Set<Character> brokenSet = new HashSet<>(); for (char c : brokenLetters.toCharArray()) { brokenSet.add(c); } String[] words = text.split(" "); int count = 0; for (String word : words) { boolean canType = true; for (char c : word.toCharArray()) { if (brokenSet.contains(c)) { canType = false; break; } } if (canType) { count++; } } return count;}Complexity
Time
O(N + M). O(M) to build the set and O(N) to iterate through all characters of the text, with each character lookup being O(1).
Space
O(N + M), where N is the length of `text` and M is the length of `brokenLetters`. O(N) for the words array and O(M) for the HashSet.
Trade-offs
Pros
Much more time-efficient than the brute-force approach.
The logic remains relatively simple and easy to follow.
Cons
Uses extra space for both the
HashSetand the array of words.Splitting the string into an array can be memory-intensive for very long
textstrings.
This approach is a micro-optimization over the HashSet method. Since we know the characters are all lowercase English letters, we can use a simple boolean array of size 26 as a direct-access lookup table. Array indexing is generally faster than hashing, providing a slight performance boost.
Algorithm
- Create a boolean array
isBrokenof size 26, initialized tofalse. - Iterate through
brokenLetters. For each characterc, setisBroken[c - 'a'] = true. - Split the
textinto an array ofwords. - Initialize a counter
countto the total number of words. - Iterate through each
wordin thewordsarray. - For each
word, iterate through its charactersc. - Check if
isBroken[c - 'a']istrue. - If it is, the word cannot be typed. Decrement
countand break the inner loop to move to the next word. - Return
count.
Walkthrough
Instead of a HashSet, we use a boolean[26] array, say isBroken, as a frequency map or a direct-access table. The index 0 corresponds to 'a', 1 to 'b', and so on. We first populate this array by iterating through brokenLetters; for each character c, we set the flag at index c - 'a' to true.
The rest of the logic is similar to the HashSet approach. We split the text into words. For each word, we check its characters. To see if a character c is broken, we simply check the value of isBroken[c - 'a']. This is an O(1) operation with very low overhead. If we find a broken character, we know the word is untypeable and move on. If a word passes the check, it contributes to the final count.
public int canBeTypedWords(String text, String brokenLetters) { boolean[] isBroken = new boolean[26]; for (char c : brokenLetters.toCharArray()) { isBroken[c - 'a'] = true; } int typeableWords = 0; String[] words = text.split(" "); for (String word : words) { boolean isWordBroken = false; for (char c : word.toCharArray()) { if (isBroken[c - 'a']) { isWordBroken = true; break; } } if (!isWordBroken) { typeableWords++; } } return typeableWords;}Complexity
Time
O(N + M). O(M) to build the boolean array and O(N) to iterate through the text. This is asymptotically the same as the HashSet approach but often faster in practice.
Space
O(N). The boolean array takes O(1) space (as its size is fixed at 26), but splitting the string still requires O(N) space for the resulting array of words.
Trade-offs
Pros
Extremely fast O(1) lookup with minimal overhead.
Constant space O(1) for the lookup table (since alphabet size is fixed).
Cons
Still requires O(N) extra space to store the array of words from splitting the text.
This is the most optimal approach in terms of both time and space. It uses the efficient boolean array for lookups and processes the text string in a single pass without splitting it into an array of words. This avoids the O(N) space overhead required by the previous approaches for storing the words.
Algorithm
- Create and populate a
boolean[26]arrayisBrokenfrombrokenLetters. - Initialize
count = 0and a flagcurrentWordIsBroken = false. - Iterate through the
textstring character by character, including a conceptual character at the end. - If the current character
cis a space or we are at the end of the string:- This marks the end of a word.
- If
currentWordIsBrokenisfalse, it means the word we just finished was typeable, so incrementcount. - Reset
currentWordIsBroken = falsefor the next word.
- If the current character
cis a letter:- Check if it's broken using the
isBrokenarray (isBroken[c - 'a']). - If it is, set
currentWordIsBroken = true.
- Check if it's broken using the
- After the loop, return
count.
Walkthrough
The key insight here is that we don't need to store all the words at once. We can process the text character by character, keeping track of the state of the current word.
We start by creating our isBroken boolean array as in the previous approach. We then initialize our count and a flag, currentWordIsBroken, which tracks if the word we are currently scanning contains a broken letter. We iterate through the text. When we see a letter, we check if it's broken. If it is, we set currentWordIsBroken to true. Once a word is marked as broken, we don't need to check its subsequent characters. When we encounter a space (or the end of the entire string), it signals the end of a word. At this point, we check our flag. If currentWordIsBroken is false, we increment our count. We then reset the flag to false to begin processing the next word. This method processes the entire text in one go, using only constant extra space for the lookup table and state flag.
public int canBeTypedWords(String text, String brokenLetters) { boolean[] isBroken = new boolean[26]; for (char c : brokenLetters.toCharArray()) { isBroken[c - 'a'] = true; } int count = 0; boolean currentWordIsBroken = false; for (int i = 0; i < text.length(); i++) { char c = text.charAt(i); if (c == ' ') { if (!currentWordIsBroken) { count++; } currentWordIsBroken = false; // Reset for the next word } else { if (isBroken[c - 'a']) { currentWordIsBroken = true; } } } // Check the last word after the loop finishes if (!currentWordIsBroken) { count++; } return count;}Complexity
Time
O(N + M). We make a single pass through `brokenLetters` (length M) and a single pass through `text` (length N).
Space
O(1). The space for the `isBroken` array is constant (size 26), and no other data structures that scale with input size are used.
Trade-offs
Pros
Optimal O(N + M) time complexity.
Optimal O(1) space complexity, as it doesn't store an intermediate array of words.
Most efficient solution for very large text inputs.
Cons
The logic can be slightly more complex to handle the state (
currentWordIsBroken) and the word boundaries correctly, especially the last word.
Solutions
Solution
class Solution {public int canBeTypedWords(String text, String brokenLetters) { boolean[] s = new boolean[26]; for (char c : brokenLetters.toCharArray()) { s[c - 'a'] = true; } int ans = 0; for (String w : text.split(" ")) { for (char c : w.toCharArray()) { if (s[c - 'a']) { --ans; break; } } ++ans; } return ans; }}class Solution: def canBeTypedWords(self, text: str, brokenLetters: str) -> int: s = set(brokenLetters) return sum(all(c not in s for c in w) for w in text . split())class Solution {public: int canBeTypedWords(string text, string brokenLetters) { bool s[26]{}; for (char &c : brokenLetters) { s[c - 'a'] = true; } int ans = 0; for (auto &w : split(text, ' ')) { for (char &c : w) { if (s[c - 'a']) { --ans; break; } } ++ans; } return ans; } vector<string> split(const string &s, char c) { vector<string> ans; string t; for (char d : s) { if (d == c) { ans.push_back(t); t.clear(); } else { t.push_back(d); } } ans.push_back(t); return ans; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.