Maximum Number of Words You Can Type

Easy
524.

Maximum Number of Words You Can Type

Maximum Number of Words You Can Type is an easy coding problem on strings and hash table, asked in Amazon and Cognizant interviews.

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 <= 10000
  • 0 <= brokenLetters.length <= 26
  • text consists of lowercase letters and single spaces, with no leading or trailing spaces.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} text
 * @param {string} brokenLetters
 * @return {number}
 */
var canBeTypedWords = function(text, brokenLetters) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 10000
  • 0 <= brokenLetters.length <= 26
  • text consists of lowercase letters and single spaces, with no leading or trailing spaces.

Hints for Maximum Number of Words You Can Type

  1. Hint 1

    Put the broken letters into a set so membership is O(1).

  2. Hint 2

    Split text on spaces and check each word independently.

  3. 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

  1. Load brokenLetters into a set (or a 26-slot boolean array).
  2. Split the text on single spaces.
  3. For each word, scan its characters; if none is broken, increment the count.
  4. 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 brokenLetters means every word counts.
  • Breaking out of the inner loop but forgetting to skip the increment double-counts broken words.
  • Searching brokenLetters with 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 count

Java

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