1935. Maximum Number of Words You Can Type
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
brokenLettersinto a set for fast lookup. - Then, it splits
textinto 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.
s = 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.
text.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.
all(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.
return 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 EvaluatorExample 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:
s = set('ad')
Now we have s = {'a', 'd'}.
Step 2: Split the Text into Words
Next, split text into individual words:
words = "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:
return 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
211class 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}
371#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};
561function 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}
37Time 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.
Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?
Recommended Readings
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Don’t Miss This!