#1935

Easy

LeetCode Problem Workspace

Maximum Number of Words You Can Type

Determine how many words can be typed on a malfunctioning keyboard with some broken keys.

Problem Statement

You are given a string text containing words separated by a single space, with no leading or trailing spaces. Additionally, a string brokenLetters is provided, which contains distinct broken letter keys. The task is to determine how many words in the string text can be fully typed using only the working keys, excluding those that require any broken letter keys.

For example, if a word contains any letter from brokenLetters, it cannot be typed. You need to iterate through each word and check if it contains any letter from the broken keys, returning the total count of words that can be fully typed.

Examples

Example 1

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

Output: 1

We cannot type "world" because the 'd' key is broken.

Example 2

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

Output: 1

We cannot type "leet" because the 'l' and 't' keys are broken.

Example 3

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

Output: 0

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.

Solution Approach

Use a Hash Set for Broken Keys

First, convert the string brokenLetters into a set for fast look-up. This allows constant time complexity when checking if a letter is broken, significantly improving efficiency when iterating through the words.

Iterate Over Each Word

For each word in the text, check whether any of its letters are in the set of broken keys. If any letter is broken, skip that word; otherwise, increment the count of words that can be typed.

Optimize With Early Exit

As soon as a broken letter is found in a word, stop checking further letters in that word. This helps minimize unnecessary computations and improves performance.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the solution depends on the length of the text and brokenLetters. The space complexity is determined by the storage of the broken letters set. With text having a maximum length of 10^4 and brokenLetters a maximum of 26, this approach is efficient with an overall time complexity of O(n*m), where n is the number of words in text and m is the maximum length of a word.

What Interviewers Usually Probe

Look for the ability to optimize the checking of each word by using a set for fast membership testing.
Ensure the candidate mentions checking each word individually instead of attempting to process all letters in one go.
Evaluate whether the candidate understands early exit in the context of word validation to improve efficiency.

Common Pitfalls or Variants

Common pitfalls

Not using a set for brokenLetters, resulting in inefficient checks.
Failing to stop checking a word once a broken letter is found, leading to unnecessary operations.
Misunderstanding the problem by trying to check all words at once instead of word-by-word.

Follow-up variants

What if the input contains a very large number of words? Optimizing the check for each word is crucial.
If the brokenLetters string is empty, the solution should immediately return the count of all words.
Consider the case where all letters in the brokenLetters string are present in a word, which would result in zero words typed.

FAQ

What is the most efficient way to check if a word can be typed given a list of broken keys?

Using a hash set to store the broken keys allows for constant time lookups while checking each letter in a word.

How do I handle the case where `brokenLetters` is empty?

If brokenLetters is empty, every word in text can be typed, so the solution should return the total number of words.

Can I optimize the word check in the "Maximum Number of Words You Can Type" problem?

Yes, optimizing the check with an early exit as soon as a broken letter is found can improve performance.

What is the time complexity of the solution?

The time complexity is O(n*m), where n is the number of words and m is the length of the longest word.

How do I solve this problem if the text has a large number of words?

You should focus on optimizing each word check using a hash set for the broken letters and implement early exits to prevent unnecessary checks.

terminal

Solution

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.

1

2

3

4

class Solution:
    def canBeTypedWords(self, text: str, brokenLetters: str) -> int:
        s = set(brokenLetters)
        return sum(all(c not in s for c in w) for w in text.split())

Continue Practicing

#1930 unique length 3 palindromic subsequences #1941 check if all characters have equal number of occurrences #1948 delete duplicate folders in system