Maximum Number of Words You Can Type

Easy

Quora

1 view

Topics:

StringsArrays

There is a malfunctioning keyboard where some letter keys do not work. All other keys on the keyboard work properly.

Given a string text of words separated by a single space (no leading or trailing spaces) and a string brokenLetters of all distinct letter keys that are broken, return the number of words in text you can fully type using this keyboard.

Example 1:

Input: text = "hello world", brokenLetters = "ad"
Output: 1
Explanation: We cannot type "world" because the 'd' key is broken.

Example 2:

Input: text = "leet code", brokenLetters = "lt"
Output: 1
Explanation: We cannot type "leet" because the 'l' and 't' keys are broken.

Example 3:

Input: text = "leet code", brokenLetters = "e"
Output: 0
Explanation: We cannot type either word because the 'e' key is broken.

Constraints:

1 <= text.length <= 10⁴
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.

Try coding it in LeetCode

Maximum Number of Words You Can Type

Easy

Quora

1 view

Topics:

StringsArrays

There is a malfunctioning keyboard where some letter keys do not work. All other keys on the keyboard work properly.

Given a string text of words separated by a single space (no leading or trailing spaces) and a string brokenLetters of all distinct letter keys that are broken, return the number of words in text you can fully type using this keyboard.

Example 1:

Input: text = "hello world", brokenLetters = "ad"
Output: 1
Explanation: We cannot type "world" because the 'd' key is broken.

Example 2:

Input: text = "leet code", brokenLetters = "lt"
Output: 1
Explanation: We cannot type "leet" because the 'l' and 't' keys are broken.

Example 3:

Input: text = "leet code", brokenLetters = "e"
Output: 0
Explanation: We cannot type either word because the 'e' key is broken.

Constraints:

1 <= text.length <= 10⁴
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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the `text` string be empty or null? What about the `brokenLetters` string?
What characters can the `text` and `brokenLetters` strings contain? Are they limited to lowercase English letters, or could they include uppercase letters, numbers, or special characters?
Is a word in `text` delimited by a single space? Could there be leading or trailing spaces, or multiple spaces between words?
If all letters in a word are broken, should that word still be counted or not?
Are there any constraints on the length of the strings `text` and `brokenLetters`? This may impact the optimal algorithm.

Brute Force Solution

Approach

The brute force solution is like trying every single possible combination. We essentially try removing each letter, one by one, and see if that fixes the problem of typing too many words.

Here's how the algorithm would work step-by-step:

Start by considering all the words you are trying to type.
For each broken key, go through all the words to type.
In each word, check if the current broken key is present.
If a broken key is present in a word, consider removing that word from the list of words you can type.
After checking all broken keys and removing words with those keys, count the number of words you can type which will be your result.

Code Implementation

def max_number_of_words_you_can_type(text, broken_letters):
    words = text.split()
    typeable_words = []

    # Iterate through each word in the given text
    for word in words:

        is_word_broken = False
        # Iterate through each broken letter to check if the current word contains any
        for broken_letter in broken_letters:

            if broken_letter in word:
                is_word_broken = True
                break

        # If the word does not contain any broken letters, add it to our typeable words list
        if not is_word_broken:

            typeable_words.append(word)

    # Return the number of words that can be typed
    return len(typeable_words)

Big(O) Analysis

Time Complexity

O(b * w * l) – The algorithm iterates through each broken key. Let 'b' be the number of broken keys. For each broken key, the algorithm iterates through all the words, where 'w' is the total number of words. Within each word, it checks if the broken key is present. Let 'l' be the average length of a word. Therefore, the total number of operations is approximately b * w * l, which results in a time complexity of O(b * w * l).

Space Complexity

O(1) – The described algorithm iterates through the input words and broken letters. It doesn't create any additional data structures that scale with the number of words or broken letters. Only a constant amount of extra space is used for boolean flags or counters during the process of checking words against broken keys, so the auxiliary space is O(1).

Optimal Solution

Approach

The core idea is to quickly figure out which letters are broken and then count how many words we can completely type given those broken letters. Instead of individually checking each word against the broken letters, we can use a shortcut to efficiently count the valid words.

Here's how the algorithm would work step-by-step:

First, figure out which letters on the keyboard are broken by putting them in a special list.
Go through each word one by one.
For each word, check if it contains any of the broken letters from our special list.
If the word does NOT contain any broken letters, we know we can type it, so increase our count of typeable words.
If the word DOES contain any broken letters, we can't type it, so we skip it and move to the next word.
After checking all the words, return the final count of words that don't have any broken letters.

Code Implementation

def maximum_number_of_words_you_can_type(text, broken_letters):
    words = text.split()
    number_of_typeable_words = 0

    broken_letters_set = set(broken_letters)

    for word in words:
        # Check if current word contains any broken letters.
        is_word_broken = False
        for char in word:
            if char in broken_letters_set:
                is_word_broken = True
                break

        # Only increment if we can type the current word.
        if not is_word_broken:
            number_of_typeable_words += 1

    return number_of_typeable_words

Big(O) Analysis

Time Complexity

O(m + n*k) – Let m be the number of broken letters and n be the number of words in the input list. Let k be the maximum length of a word. First, we iterate through the string of broken letters, which takes O(m) time. Then, for each of the n words, we potentially iterate through the entire word to check if it contains any broken letters. In the worst case, we might iterate through the entire word (length k) for each of the n words, leading to O(n*k) time. Therefore, the overall time complexity is O(m + n*k).

Space Complexity

O(D) – The algorithm uses a list or set to store the broken letters. The size of this list depends on the number of distinct broken letters, which we'll denote as D. Therefore, the auxiliary space required is proportional to the number of distinct broken letters. Consequently, the space complexity is O(D).

Edge Cases

Case	How to Handle
text is null or empty	Return 0 since no words can be typed.
brokenLetters is null or empty	Return the number of words in text, since all letters are typeable.
text contains only whitespace	Return 0, as there are no valid words.
brokenLetters contains all lowercase letters	Return 0 since no word can be typed
text contains words with punctuation	Split the text by spaces and iterate, treating punctuation as part of the word, it will only fail if punctuation contains broken letters.
text contains very long words	Ensure algorithm scales correctly, preventing performance issues in checking if the long word can be typed.
text contains leading or trailing spaces	Trim the text to remove leading and trailing spaces before splitting.
brokenLetters contains duplicate characters	The algorithm should treat this as only checking for the unique broken letters, not being affected by duplicates.