1935. Maximum Number of Words You Can Type

EasyHash TableString
Leetcode Link

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.

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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

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

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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Recommended Readings

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.