What is the time complexity of Approach 1: Hash Set?

The time complexity is O(N), where N is the total number of characters in the text string. We iterate through the text once to check characters against the set.

Why use a Boolean Array over a Hash Set?

A Boolean Array is often more performant for fixed-size alphabets (like 26 lowercase letters) because it uses direct indexing without the overhead of hash calculations or collision handling.

How does Bitmasking work in this problem?

Bitmasking uses an integer where each bit represents a letter. We create a mask for broken letters and a mask for each word. If the bitwise AND of these masks is zero, the word contains no broken letters.

What is the space complexity for all approaches?

All approaches have O(1) auxiliary space complexity because the storage required (Set, Array, or Integer) is bounded by the fixed size of the alphabet (26 letters).

Maximum Number of Words You Can Type

Difficulty: Easy | Acceptance: 82.90% | Paid: No Topics: Hash Table, String

There is a malfunctioning keyboard where some letter keys do not work. All other keys on the keyboard that are not broken will work. 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.

Examples
Constraints
Approach 1: Hash Set
Approach 2: Boolean Array
Approach 3: Bitmasking

Examples

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 both '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 <= 10⁴
0 <= brokenLetters.length <= 26
text consists of words separated by a single space.
There are no leading or trailing spaces.
Every word only contains lowercase English letters.
brokenLetters consists of distinct lowercase English letters.

Approach 1: Hash Set

Intuition Convert the string of broken letters into a Hash Set for O(1) lookups. Then, iterate through each word in the text and check if any character exists in the set.

Steps

Store all characters from brokenLetters in a set.
Split the input text into an array of words.
Iterate through each word. For every word, check if any of its characters are present in the broken letters set.
If a word contains no broken letters, increment the result counter.

python

Complexity

Time: O(N), where N is the total number of characters in text. We process each character once.
Space: O(1), since the set size is bounded by 26 (alphabet size).
Notes: Simple and readable, utilizing standard library data structures.

Approach 2: Boolean Array

Intuition Since the input consists only of lowercase English letters, we can use a fixed-size boolean array of length 26 to track broken letters. This avoids the overhead of hashing required by a Hash Set.

Steps

Initialize a boolean array of size 26 to false.
Iterate through brokenLetters and mark the corresponding index (e.g., char - 'a') as true.
Split text into words.
For each word, check every character. If the character’s index in the boolean array is true, the word is broken.
Count words that have no broken characters.

python

Complexity

Time: O(N), where N is the total number of characters in text.
Space: O(1), fixed array of size 26.
Notes: Slightly more performant than a Hash Set due to direct indexing and lack of collision handling.

Approach 3: Bitmasking

Intuition Represent the set of broken letters as a bitmask (an integer). Each bit corresponds to a letter in the alphabet. We can also create a mask for each word. If the bitwise AND of the word’s mask and the broken mask is zero, the word can be typed.

Steps

Calculate the brokenMask by setting the bit corresponding to each letter in brokenLetters.
Split the text into words.
For each word, calculate its wordMask by setting bits for its characters.
Check if (wordMask & brokenMask) == 0. If true, the word is valid.

python

Complexity

Time: O(N), where N is the total number of characters in text.
Space: O(1), using only a few integer variables.
Notes: Highly efficient for low-alphabet constraints, minimizing memory usage.