algoadvance

Leetcode 1935. Maximum Number of Words You Can Type

Problem Statement

You are given a string text of words that are separated by one or more spaces, and a string brokenLetters of lowercase English letters that contains some broken letters.

Return the number of words in the text you can fully type using the keyboard provided that the broken letters might not work properly for typing. A word is defined as a sequence of non-space characters.

Example

• Example 1:
  • Input: text = "hello world", brokenLetters = "ad"
  • Output: 1
  • Explanation: You can only type the word “world”.
• Example 2:
  • Input: text = "leet code", brokenLetters = "lt"
  • Output: 1
  • Explanation: You can only type the word “code”.
• Example 3:
  • Input: text = "leet code", brokenLetters = "e"
  • Output: 0
  • Explanation: You cannot type any word because “e” is broken.

Clarifying Questions

1. Can the text contain uppercase letters or punctuation?
   • No, the text only contains lowercase English letters and spaces.
2. Can the brokenLetters string be empty?
   • Yes, if brokenLetters is empty, then all letters are functional, and all words can be typed.
3. Are there any constraints on the length of text and brokenLetters?
   • Both text and brokenLetters can be of length up to 10,000.

Strategy

1. Convert Broken Letters into Set: Use a set for brokenLetters to enable O(1) average lookup time.
2. Split Text into Words: Split the text based on spaces to process each word separately.
3. Check Each Word: For each word, check if any character is in the brokenLetters set. If not, it can be typed.
4. Count Typable Words: Increment the count for each word that can be fully typed.

Steps:

1. Convert the brokenLetters string into a set for efficient lookup.
2. Split the text by spaces to get individual words.
3. For each word, check if any of its characters are in the brokenLetters set.
4. If a word doesn’t contain any broken letters, increment the count.

Time Complexity

• Conversion to Set: O(B), where B is the length of brokenLetters.
• Splitting Text into Words: O(T + W), where T is the length of the text and W is the number of words.
• Checking Each Word: O(W * L), where L is the average length of the words.

Overall, the time complexity is O(T + B + W * L).

Code

Here’s how we can implement this in C++:

#include <iostream>
#include <unordered_set>
#include <sstream>
using namespace std;

int canBeTypedWords(string text, string brokenLetters) {
    unordered_set<char> broken(brokenLetters.begin(), brokenLetters.end());
    istringstream iss(text);
    string word;
    int count = 0;
    bool canType = true;

    while (iss >> word) {
        canType = true;
        for (char c : word) {
            if (broken.find(c) != broken.end()) {
                canType = false;
                break;
            }
        }
        if (canType) count++;
    }

    return count;
}

int main() {
    // Example usage:
    string text = "hello world";
    string brokenLetters = "ad";
    cout << canBeTypedWords(text, brokenLetters) << endl; // Output: 1
    return 0;
}

This code uses a set to store broken letters for fast lookup and processes each word by checking each character to see if it’s a broken letter. If a word doesn’t contain any broken letters, it is considered typable.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?