Leetcode 1935: Maximum Number of Words You Can Type

Input: The input consists of two strings: 'text' containing words separated by spaces, and 'brokenLetters' containing distinct lowercase English letters.

Example: text = "apple orange", brokenLetters = "a"

Constraints:

• 1 <= text.length <= 10^4

• 0 <= brokenLetters.length <= 26

• text consists of words separated by a single space without leading or trailing spaces.

• Each word only consists of lowercase English letters.

• brokenLetters consists of distinct lowercase English letters.

Output: Return the number of words in 'text' that can be fully typed using the working keys.

Example: 1

Constraints:

Goal: To count the number of words in 'text' that do not contain any broken letters.

Steps:

• Iterate over each word in 'text'.

• For each word, check if it contains any letter from 'brokenLetters'.

• If a word can be fully typed (contains no broken letters), increment the count.

Goal: We need an efficient solution that works with text lengths up to 10^4.

Steps:

• The text string will have a length between 1 and 10,000.

• The brokenLetters string will contain distinct lowercase English letters (0 to 26 characters).

Assumptions:

• The text string is guaranteed to have words separated by single spaces.

• The brokenLetters string can be empty, which means all letters are usable.

• Input: text = "apple orange", brokenLetters = "a"

• Explanation: The word 'apple' cannot be typed because it contains the broken letter 'a', but 'orange' can be typed. Hence, the output is 1.

Approach: We will process each word and check if it contains any broken letter. If it doesn't, we increment the count.

Observations:

• We need to check each word in the text for broken letters.

• We can use a set to store the broken letters and efficiently check if any letter in a word is broken.

Steps:

• Convert the brokenLetters string into a set for O(1) lookup time.

• Iterate through each word in 'text'.

• For each word, check if any character is in the set of brokenLetters.

• If a word has no broken letters, increment the counter.

Empty Inputs:

• If 'brokenLetters' is empty, all words are typeable.

Large Inputs:

• The solution must handle the maximum length of the text efficiently.

Special Values:

• If a word is empty (which shouldn't occur as per constraints), it should be considered typeable.

Constraints:

• The solution must run in O(n) time where n is the length of the text string.

int canBeTypedWords(string text, string brokenLetters) {
    bool broken[26] = {};
    for (auto ch : brokenLetters)
        broken[ch - 'a'] = true;
    int res = 0, cnt = 0;
    for (auto ch : text)
        if (ch == ' ') {
            res += cnt == 0;
            cnt = 0;
        }
        else
            cnt += broken[ch - 'a'];
    return res + (cnt == 0);
}

1 : Function Header

int canBeTypedWords(string text, string brokenLetters) {

Defines the function `canBeTypedWords`, which takes two strings: `text` (the input text) and `brokenLetters` (the letters that cannot be used). It returns an integer representing how many words can be typed without using any broken letters.

2 : Array Initialization

    bool broken[26] = {};

Initializes a boolean array `broken[26]` to mark which letters are broken. The array is of size 26, corresponding to each letter of the alphabet.

3 : Loop Through Broken Letters

    for (auto ch : brokenLetters)

Loops through each character in the `brokenLetters` string to mark the broken letters in the `broken` array.

4 : Mark Broken Letters

        broken[ch - 'a'] = true;

Marks the respective index of the `broken` array as `true` for each broken letter in the `brokenLetters` string.

5 : Variable Initialization

    int res = 0, cnt = 0;

Initializes two variables: `res` (the result to count valid words) and `cnt` (the counter for broken letters in a word).

6 : Loop Through Text

    for (auto ch : text)

Starts a loop that iterates through each character in the input string `text`.

7 : Space Character Check

        if (ch == ' ') {

Checks if the current character is a space, indicating the end of a word.

8 : Valid Word Check

            res += cnt == 0;

If the word contains no broken letters (`cnt == 0`), increments the result `res`.

9 : Reset Counter

            cnt = 0;

Resets the `cnt` variable to 0 to start counting broken letters for the next word.

10 : Non-Space Character Check

        else

Handles the case when the current character is not a space (i.e., it's part of a word).

11 : Broken Letter Count

            cnt += broken[ch - 'a'];

Increments the `cnt` variable if the current character is a broken letter.

12 : Return Statement

    return res + (cnt == 0);

Returns the final count of valid words, adding 1 if the last word is valid (i.e., `cnt == 0`).

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n), where n is the number of characters in the text, because we need to check each character against the broken letters.

Best Case: O(k)

Worst Case: O(k)

Description: The space complexity is O(k), where k is the number of distinct broken letters (at most 26).

Leetcode 1935: Maximum Number of Words You Can Type

Explore →