1935. Maximum Number of Words You Can Type
Description
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 <= 104
0 <= brokenLetters.length <= 26
text
consists of words separated by a single space without any leading or trailing spaces.- Each word only consists of lowercase English letters.
brokenLetters
consists of distinct lowercase English letters.
Solutions
Solution 1: 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$.
1 2 3 4 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|