Maximum Number of Words You Can Type — Problem & Solution
Maximum Number of Words You Can Type solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Maximum Number of Words You Can Type is an easy coding problem on strings and hash table, asked in Amazon and Cognizant interviews.
- Difficulty: Easy
- Topics: Strings, Hash Table
- Asked at: Amazon, Cognizant
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A keyboard has some broken letter keys. Given text — words separated by single spaces — and brokenLetters listing the distinct broken keys, return how many words can still be typed in full.
Example 1
Input: text = "hello world", brokenLetters = "ad"
Output: 1
Explanation: "world" contains a d, so only "hello" can be typed.
Example 2
Input: text = "leet code", brokenLetters = "lt"
Output: 1
Example 3
Input: text = "leet code", brokenLetters = "e"
Output: 0
Constraints
1 <= text.length <= 100000 <= brokenLetters.length <= 26text consists of lowercase letters and single spaces, with no leading or trailing spaces.
Hints for Maximum Number of Words You Can Type
Hint 1
Put the broken letters into a set so membership is O(1).
Hint 2
Split
texton spaces and check each word independently.Hint 3
A word counts only if none of its letters is broken.
How to solve Maximum Number of Words You Can Type
Each word is independently typeable or not, so the answer is a count over an O(1) membership test per character.
Approach
- Load
brokenLettersinto a set (or a 26-slot boolean array). - Split the text on single spaces.
- For each word, scan its characters; if none is broken, increment the count.
- Return the count.
Why it works
Typeability is a conjunction over the word's characters, and set membership answers each character in constant time, so the total work is linear in the text length.
Complexity
- Time —
O(n) - Space —
O(1) — the set holds at most 26 letters
Pitfalls
- An empty
brokenLettersmeans every word counts. - Breaking out of the inner loop but forgetting to skip the increment double-counts broken words.
- Searching
brokenLetterswith a linear scan per character is still fine at 26 letters, but a set keeps it obviously linear.
Reference solution
Python
def canBeTypedWords(text: str, brokenLetters: str) -> int:
broken = set(brokenLetters)
count = 0
for w in text.split(" "):
if not any(c in broken for c in w):
count += 1
return countJava
public static int canBeTypedWords(String text, String brokenLetters) {
boolean[] broken = new boolean[26];
for (int i = 0; i < brokenLetters.length(); i++) broken[brokenLetters.charAt(i) - 'a'] = true;
int count = 0;
for (String w : text.split(" ")) {
boolean ok = true;
for (int i = 0; i < w.length(); i++) {
if (broken[w.charAt(i) - 'a']) { ok = false; break; }
}
if (ok) count++;
}
return count;
}C++
int canBeTypedWords(string text, string brokenLetters) {
bool broken[26] = { false };
for (char c : brokenLetters) broken[c - 'a'] = true;
int count = 0;
bool ok = true;
for (size_t i = 0; i <= text.size(); i++) {
if (i == text.size() || text[i] == ' ') {
if (ok) count++;
ok = true;
} else if (broken[text[i] - 'a']) {
ok = false;
}
}
return count;
}JavaScript
var canBeTypedWords = function(text, brokenLetters) {
const broken = {};
for (let i = 0; i < brokenLetters.length; i++) broken[brokenLetters.charAt(i)] = true;
const words = text.split(" ");
let count = 0;
for (let i = 0; i < words.length; i++) {
let ok = true;
for (let j = 0; j < words[i].length; j++) {
if (broken[words[i].charAt(j)] === true) { ok = false; break; }
}
if (ok) count++;
}
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets