Maximum Number of Words You Can Type

Maximum Number of Words You Can Type - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: text = "hello world", brokenLetters = "ad"

› Output: 1

💡 Note: We can type "hello" (no 'a' or 'd'), but cannot type "world" (contains 'd'). So 1 word can be typed.

Example 2 — Multiple Broken Letters

$ Input: text = "leet code", brokenLetters = "lt"

› Output: 1

💡 Note: We cannot type "leet" (contains 'l' and 't'), but can type "code" (no 'l' or 't'). So 1 word can be typed.

Example 3 — No Broken Letters

$ Input: text = "leet code", brokenLetters = ""

› Output: 2

💡 Note: No keys are broken, so we can type all words: "leet" and "code". So 2 words can be typed.

Constraints

1 ≤ text.length ≤ 10⁴
0 ≤ brokenLetters.length ≤ 26
text consists of words separated by a single space without any leading or trailing spaces
Each word consists of only lowercase English letters
brokenLetters consists of distinct lowercase English letters

Visualization

Tap to expand

Asked in

a Amazon 15 M Microsoft 8

The key insight is to use a hash set to store broken letters for O(1) lookup time instead of scanning the broken letters string repeatedly. Best approach is hash set optimization: Time: O(n×m), Space: O(k) where n=words, m=avg word length, k=broken letters.

Common Approaches

Approach	Time	Space	Notes
✓ Hash Set Optimization	O(n × m)	O(k)	Use a hash set to store broken letters for O(1) lookup time
Brute Force	O(n × m × k)	O(1)	Check each character of every word against the broken letters string

Hash Set Optimization — Algorithm Steps

Create hash set from brokenLetters string
Split text into words
For each word, check if any character is in broken set
Count words with no broken characters

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Hash Set

Store broken letters in hash set for instant lookup

Check Words

For each word, check characters against hash set

Count Valid

Count words with no broken characters

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int solution(char* text, char* brokenLetters) {
    if (strlen(text) == 0) return 0;
    
    // Create boolean array for broken letters (assuming lowercase a-z)
    bool broken[26] = {false};
    for (int i = 0; i < strlen(brokenLetters); i++) {
        broken[brokenLetters[i] - 'a'] = true;
    }
    
    char* textCopy = strdup(text);
    char* word = strtok(textCopy, " ");
    int count = 0;
    
    while (word != NULL) {
        bool canType = true;
        for (int i = 0; i < strlen(word); i++) {
            if (broken[word[i] - 'a']) {
                canType = false;
                break;
            }
        }
        
        if (canType) {
            count++;
        }
        
        word = strtok(NULL, " ");
    }
    
    free(textCopy);
    return count;
}

int main() {
    char text[1001], brokenLetters[27];
    fgets(text, sizeof(text), stdin);
    text[strcspn(text, "\n")] = 0;
    fgets(brokenLetters, sizeof(brokenLetters), stdin);
    brokenLetters[strcspn(brokenLetters, "\n")] = 0;
    
    int result = solution(text, brokenLetters);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m)

n words × m average word length, with O(1) hash set lookups

✓ Linear Growth

Space Complexity

O(k)

Hash set stores k broken letters

✓ Linear Space

12.5K Views

Medium Frequency

~10 min Avg. Time

420 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Set Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler