1935. Maximum Number of Words You Can Type

EasyHash TableString

Problem Description

In the given problem, you are presented with a scenario where you have a keyboard with some malfunctioning letter keys. These keys are broken and do not work at all, while the rest of the keyboard is functioning properly. You're provided with a string called text that contains words separated by single spaces. There's no extra spacing at the beginning or end of this string. You're also given another string named brokenLetters, which contains unique letters that represent the broken keys on the keyboard.

Your task is to determine how many of the words in text you could type on this keyboard. In other words, a word can be typed if it doesn't contain any of the letters from brokenLetters. The goal is to return the count of such fully typable words from the original string text.

Intuition

To find a solution to the problem, the straightforward approach is to use a set to track all the broken keys. A set is chosen because it allows O(1) complexity for checking the existence of a character, which helps in efficiently determining whether a character in a word is broken.

The next step is to iterate over each word in the provided text. As we check each character in the word, we use the set to verify if that character corresponds to a broken key. If we don't find any broken letters in a word, it indicates that the word can be fully typed using the keyboard and therefore, we count that word as typable. Conversely, if even one character in the word matches a broken letter, the word can't be typed at all.

The solution code applies this logic to count the number of words that can be typed. It uses list comprehension paired with the all() function to efficiently test each word. Here's a breakdown of what the solution does:

It first converts brokenLetters into a set for fast lookup.
Then, it splits text into individual words.
For each word, it checks whether all the characters are not in the set of broken letters using all(c not in s for c in w).
The sum() function accumulates the total count of words that satisfy the condition.

By completing the traversal and these checks, we can return the total number of words that can be typed, which is the answer the problem is asking for.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27

1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30

1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

["jk", "mno"]["jm", "kn", "lo"]["jklmnp"]["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don’t know

Solution Approach

The solution uses a simple but effective approach utilizing Python's built-in data structures and functions.

Step 1: Create a Set of Broken Letters

Firstly, the code creates a set from brokenLetters. A set is an appropriate data structure because it allows for constant time complexity, O(1), for lookups.

1s = set(brokenLetters)

Step 2: Split the Text into Words

The text string is then split into individual words using the split() method, which by default, separates words based on spaces.

1text.split()

Step 3: Check Each Word

For each word in the text, we check if all characters c are not in the set s. This is done using the all() function alongside a generator expression. The all() function returns True if all elements of the iterable (in this case, the generator expression) are true. If any character c is found in the set s (broken letters), all() would return False for that word.

1all(c not in s for c in w) for w in text.split()

Step 4: Count the Typable Words

We then use the sum() function to count the number of words for which the all() function returned True. This results in the total number of words from the text that can be typed using the keyboard despite the broken keys.

1return sum(all(c not in s for c in w) for w in text.split())

Algorithm

The algorithm essentially iterates through each word and checks each character only once. For a text of n words and assuming the longest word has m characters, the algorithm would have a time complexity of O(m * n), where m * n represents the total number of characters we need to check. The space complexity of this algorithm is O(b), where b is the number of broken letters because we are creating a set to hold these letters. However, since the number of letters in English is constant (26 letters), and brokenLetters cannot be longer than that, the set is of a constant size, and the space complexity can also be considered O(1).

The solution is clean and efficient; it uses basic data structures in Python and leverages their properties, such as the set for fast lookups and the all() function to check the validity of each word.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which algorithm should you use to find a node that is close to the root of the tree?

Depth First SearchBreadth First Search

I don’t know

Example Walkthrough

Let's take a simple example to walk through the solution approach. Suppose we have the text text = "hello world program" and let's say the brokenLetters = "ad".

Step 1: Create a Set of Broken Letters

Create a set from brokenLetters. Our set s will look like this:

1s = set('ad')

Now we have s = {'a', 'd'}.

Step 2: Split the Text into Words

Next, split text into individual words:

1words = "hello world program".split()

After the split, words will be ['hello', 'world', 'program'].

Step 3: Check Each Word

Now, check each word in words to see if any of the characters are in set s. For 'hello', applying all(c not in s for c in 'hello'):

'h' is not in s, continue.
'e' is not in s, continue.
'l' is not in s, continue.
'l' is not in s, continue.
'o' is not in s, continue. Since all characters passed the check, 'hello' can be typed.

For 'world', applying all(c not in s for c in 'world'):

'w' is not in s, continue.
'o' is not in s, continue.
'r' is not in s, continue.
'l' is not in s, continue.
'd' is in s, stop. Since 'd' is a broken letter, 'world' cannot be typed.

For 'program', applying all(c not in s for c in 'program'):

'p' is not in s, continue.
'r' is not in s, continue.
'o' is not in s, continue.
'g' is not in s, continue.
'r' is not in s, continue.
'a' is in s, stop. Since 'a' is a broken letter, 'program' cannot be typed.

Step 4: Count the Typable Words

Finally, we count the typable words. Only the first word, 'hello', can be typed with the broken keys 'ad'. So, using the sum() function:

1return sum(all(c not in s for c in w) for w in words)

The code will evaluate to 1, since only one word in the array can be typed.

Therefore, the final answer for the text text = "hello world program" with brokenLetters = "ad" is 1, as only the word "hello" can be typed.

Solution Implementation

1class Solution:
2    def canBeTypedWords(self, text: str, brokenLetters: str) -> int:
3        # Convert the string of broken letters into a set for O(1) lookup times
4        broken_letters_set = set(brokenLetters)
5      
6        # Split the input text by spaces to get individual words
7        words = text.split()
8      
9        # Initialize a variable to count the number of words that can be typed
10        count = 0
11      
12        # Iterate through each word in the list of words
13        for word in words:
14            # Check if all characters in the current word are not in the set of broken letters
15            if all(char not in broken_letters_set for char in word):
16                # If the word can be typed, increment the count
17                count += 1
18      
19        # Return the final count of words that can be typed without using any broken letters
20        return count
21

1class Solution {
2    // Method to count how many words in a given text can be typed 
3    // using a keyboard with some broken letters.
4    public int canBeTypedWords(String text, String brokenLetters) {
5        // Array to keep track of which letters are broken.
6        boolean[] isBroken = new boolean[26];
7      
8        // Populate the isBroken array; a 'true' value means the letter is broken.
9        for (char letter : brokenLetters.toCharArray()) {
10            isBroken[letter - 'a'] = true;
11        }
12      
13        int count = 0; // This will store the number of words that can be typed.
14        // Split the input text into words and iterate through them.
15        for (String word : text.split(" ")) {
16            boolean canTypeWord = true; // Flag to check if the current word can be typed.
17          
18            // Check each character in the word to see if it is broken.
19            for (char letter : word.toCharArray()) {
20                // If the letter is broken, set the flag to false and break out of the loop.
21                if (isBroken[letter - 'a']) {
22                    canTypeWord = false;
23                    break;
24                }
25            }
26          
27            // If the word can be typed (none of its letters are broken), increase the count.
28            if (canTypeWord) {
29                count++;
30            }
31        }
32      
33        // Return the total count of words that can be typed.
34        return count;
35    }
36}
37

1#include <vector>
2#include <string>
3
4class Solution {
5public:
6    // Function to count the number of words that can be typed with broken letters
7    int canBeTypedWords(std::string text, std::string brokenLetters) {
8        // Initialize an array to mark the broken letters
9        bool brokenStatus[26] = {false};
10        // Mark the broken letters in the array
11        for (char& c : brokenLetters) {
12            brokenStatus[c - 'a'] = true;
13        }
14
15        // Variable to store the count of words that can be typed
16        int count = 0;
17        // Split the input text into words and process each word
18        for (auto& word : split(text, ' ')) {
19            bool canTypeWord = true;
20            // Check each character in the word
21            for (char& c : word) {
22                // If the character is a broken letter, skip the word
23                if (brokenStatus[c - 'a']) {
24                    canTypeWord = false;
25                    break;
26                }
27            }
28            // If all characters are typable, increase the count
29            if (canTypeWord) {
30                count++;
31            }
32        }
33        return count;
34    }
35
36    // Helper function to split a string into words based on a delimiter
37    std::vector<std::string> split(const std::string& str, char delimiter) {
38        std::vector<std::string> result;
39        std::string currentWord;
40        // Iterate over each character in the string
41        for (char d : str) {
42            // If the delimiter is encountered, add the current word to the result
43            if (d == delimiter) {
44                result.push_back(currentWord);
45                currentWord.clear();
46            } else {
47                // Add the character to the current word
48                currentWord.push_back(d);
49            }
50        }
51        // Add the last word to the result
52        result.push_back(currentWord);
53        return result;
54    }
55};
56

1function canBeTypedWords(text: string, brokenLetters: string): number {
2    // Create an array to keep track of broken letters.
3    const brokenStatus: boolean[] = new Array(26).fill(false);
4  
5    // Iterate through the list of broken letters and update their
6    // status in the boolean array. 'true' means the letter is broken.
7    for (const letter of brokenLetters) {
8        const index = letter.charCodeAt(0) - 'a'.charCodeAt(0);
9        brokenStatus[index] = true;
10    }
11  
12    // Initialize a counter for the number of words that can be typed.
13    let count = 0;
14  
15    // Split the text into words and iterate through each word.
16    for (const word of text.split(' ')) {
17        let canTypeWord = true; // Flag indicating if the word can be typed.
18      
19        // Check each character of the word.
20        for (const char of word) {
21            // If the character corresponds to a broken letter, mark the word as untypable.
22            if (brokenStatus[char.charCodeAt(0) - 'a'.charCodeAt(0)]) {
23                canTypeWord = false; // Cannot type this word, so set the flag to false.
24                break; // No need to check other characters.
25            }
26        }
27      
28        // If the word can be typed (no broken letter found), increment the counter.
29        if (canTypeWord) {
30            count++;
31        }
32    }
33  
34    // Return the total number of words that can be typed.
35    return count;
36}
37

Not Sure What to Study? Take the 2-min Quiz：

Time and Space Complexity

The time complexity of the provided code is O(n), where n is the length of the input string text. This is because the code iterates through each character of every word in text exactly once in the worst case, to check if any of the characters is in the set of broken letters.

The space complexity is O(1) or O(|Σ|) where |Σ| represents the size of the set of unique letters, which in the context of the English alphabet is a constant 26. This space is used to store the set of broken letters. Since the size of this set is limited by the number of unique characters in the alphabet, and does not grow with the size of the input text, it is considered a constant space complexity.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Pre-order traversalPost-order traversalIn-order traversalLevel-order traversal

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

1935. Maximum Number of Words You Can Type

Problem Description

Intuition

Solution Approach

Step 1: Create a Set of Broken Letters

Step 2: Split the Text into Words

Step 3: Check Each Word

Step 4: Count the Typable Words

Algorithm

Example Walkthrough

Step 1: Create a Set of Broken Letters