# Maximum Number of Words You Can Type
**Difficulty:** EASY
[External](https://leetcode.com/problems/maximum-number-of-words-you-can-type)
Canonical: https://scaleengineer.com/dsa/problems/maximum-number-of-words-you-can-type
**Data structures:** Hash Table, String
**Companies:** [Quora](https://scaleengineer.com/companies/quora)
---
## Problem
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 <= 104`
* `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.

# Approaches
## Brute-Force with String Searching
This approach directly translates the problem statement into code. It iterates through each word and, for every character in that word, it performs a linear scan through the `brokenLetters` string to see if there's a match. While straightforward, this method is computationally expensive.
**Time:** O(N * M), where N is the length of `text` and M is the length of `brokenLetters`. For each character in `text`, we might perform a search through `brokenLetters`, leading to a multiplicative complexity. · **Space:** O(N), where N is the length of the `text`. This is because splitting the string creates a new array of words which, in the worst case, can have a total size proportional to the original string.
**Pros:** Very simple to conceptualize and implement.; Requires minimal auxiliary data structures.
**Cons:** Highly inefficient due to the triple nested loop structure (iterating words, characters in a word, and characters in brokenLetters).; The time complexity is poor, making it unsuitable for large inputs.
### Explanation
The core idea is to check every character of every word against every single broken letter. 

We begin by splitting the input `text` into an array of individual words. We then loop through this array. For each word, we assume it's typeable until proven otherwise. We do this by iterating through its characters. For each character, we perform another iteration through all the `brokenLetters`. If a match is found, we immediately know the word is not typeable, so we mark it as such and stop checking this particular word, moving on to the next one. If we manage to check all characters of a word without finding any broken letters, we increment our counter of typeable words.

```java
public int canBeTypedWords(String text, String brokenLetters) {
    String[] words = text.split(" ");
    int count = 0;
    for (String word : words) {
        boolean canType = true;
        for (char c : word.toCharArray()) {
            // Inefficiently check against brokenLetters string
            if (brokenLetters.indexOf(c) != -1) {
                canType = false;
                break;
            }
        }
        if (canType) {
            count++;
        }
    }
    return count;
}
```
### Algorithm
- Split the `text` string into an array of `words`.
- Initialize a counter `count` to zero.
- Iterate through each `word` in the `words` array.
- For each `word`, set a flag `canType` to `true`.
- Start a nested loop to iterate through each character `c` of the current `word`.
- Inside this, start another nested loop to iterate through each character `b` in `brokenLetters`.
- If `c` is equal to `b`, it means the word contains a broken letter. Set `canType` to `false` and break from the inner loops for this word.
- If the loop for a word completes and `canType` is still `true`, increment `count`.
- Return `count` after checking all words.

## Optimized Lookup with HashSet
This approach improves upon the brute-force method by optimizing the lookup of broken letters. By storing the `brokenLetters` in a `HashSet`, we can check if a character is broken in constant average time, `O(1)`, instead of linear time. This significantly reduces the overall time complexity.
**Time:** O(N + M). O(M) to build the set and O(N) to iterate through all characters of the text, with each character lookup being O(1). · **Space:** O(N + M), where N is the length of `text` and M is the length of `brokenLetters`. O(N) for the words array and O(M) for the HashSet.
**Pros:** Much more time-efficient than the brute-force approach.; The logic remains relatively simple and easy to follow.
**Cons:** Uses extra space for both the `HashSet` and the array of words.; Splitting the string into an array can be memory-intensive for very long `text` strings.
### Explanation
The main bottleneck in the brute-force approach is the repeated scanning of the `brokenLetters` string. We can eliminate this by pre-processing `brokenLetters` into a more efficient data structure. A `HashSet` is ideal for this, as it provides average O(1) time complexity for containment checks (`contains()` method).

First, we iterate through `brokenLetters` and add each character to a `HashSet`. Then, we proceed as before: split `text` into words and iterate through them. For each character of a word, we now use the `HashSet`'s `contains()` method to check if it's a broken letter. This check is much faster. If a broken letter is found, we stop processing the current word and move to the next. If a word is traversed completely without any hits from the `HashSet`, it's deemed typeable, and we increment our count.

```java
import java.util.HashSet;
import java.util.Set;

public int canBeTypedWords(String text, String brokenLetters) {
    Set<Character> brokenSet = new HashSet<>();
    for (char c : brokenLetters.toCharArray()) {
        brokenSet.add(c);
    }

    String[] words = text.split(" ");
    int count = 0;
    for (String word : words) {
        boolean canType = true;
        for (char c : word.toCharArray()) {
            if (brokenSet.contains(c)) {
                canType = false;
                break;
            }
        }
        if (canType) {
            count++;
        }
    }
    return count;
}
```
### Algorithm
- Create a `HashSet<Character>` and populate it with all characters from the `brokenLetters` string.
- Split the `text` into an array of `words`.
- Initialize a counter `count` to zero.
- Iterate through each `word` in the `words` array.
- For each `word`, assume it is typeable by setting a flag `canType` to `true`.
- Iterate through the characters `c` of the current `word`.
- For each character `c`, check if it is present in the `HashSet`. This is an O(1) average time operation.
- If `c` is in the set, set `canType` to `false` and break the inner loop.
- If the word's loop finishes and `canType` is still `true`, increment `count`.
- Return `count`.

## Optimized Lookup with Boolean Array
This approach is a micro-optimization over the `HashSet` method. Since we know the characters are all lowercase English letters, we can use a simple boolean array of size 26 as a direct-access lookup table. Array indexing is generally faster than hashing, providing a slight performance boost.
**Time:** O(N + M). O(M) to build the boolean array and O(N) to iterate through the text. This is asymptotically the same as the HashSet approach but often faster in practice. · **Space:** O(N). The boolean array takes O(1) space (as its size is fixed at 26), but splitting the string still requires O(N) space for the resulting array of words.
**Pros:** Extremely fast O(1) lookup with minimal overhead.; Constant space O(1) for the lookup table (since alphabet size is fixed).
**Cons:** Still requires O(N) extra space to store the array of words from splitting the text.
### Explanation
Instead of a `HashSet`, we use a `boolean[26]` array, say `isBroken`, as a frequency map or a direct-access table. The index `0` corresponds to 'a', `1` to 'b', and so on. We first populate this array by iterating through `brokenLetters`; for each character `c`, we set the flag at index `c - 'a'` to `true`.

The rest of the logic is similar to the `HashSet` approach. We split the text into words. For each word, we check its characters. To see if a character `c` is broken, we simply check the value of `isBroken[c - 'a']`. This is an O(1) operation with very low overhead. If we find a broken character, we know the word is untypeable and move on. If a word passes the check, it contributes to the final count.

```java
public int canBeTypedWords(String text, String brokenLetters) {
    boolean[] isBroken = new boolean[26];
    for (char c : brokenLetters.toCharArray()) {
        isBroken[c - 'a'] = true;
    }

    int typeableWords = 0;
    String[] words = text.split(" ");
    for (String word : words) {
        boolean isWordBroken = false;
        for (char c : word.toCharArray()) {
            if (isBroken[c - 'a']) {
                isWordBroken = true;
                break;
            }
        }
        if (!isWordBroken) {
            typeableWords++;
        }
    }
    return typeableWords;
}
```
### Algorithm
- Create a boolean array `isBroken` of size 26, initialized to `false`.
- Iterate through `brokenLetters`. For each character `c`, set `isBroken[c - 'a'] = true`.
- Split the `text` into an array of `words`.
- Initialize a counter `count` to the total number of words.
- Iterate through each `word` in the `words` array.
- For each `word`, iterate through its characters `c`.
- Check if `isBroken[c - 'a']` is `true`. 
- If it is, the word cannot be typed. Decrement `count` and break the inner loop to move to the next word.
- Return `count`.

## Most Efficient: Single Pass with Constant Space
This is the most optimal approach in terms of both time and space. It uses the efficient boolean array for lookups and processes the `text` string in a single pass without splitting it into an array of words. This avoids the O(N) space overhead required by the previous approaches for storing the words.
**Time:** O(N + M). We make a single pass through `brokenLetters` (length M) and a single pass through `text` (length N). · **Space:** O(1). The space for the `isBroken` array is constant (size 26), and no other data structures that scale with input size are used.
**Pros:** Optimal O(N + M) time complexity.; Optimal O(1) space complexity, as it doesn't store an intermediate array of words.; Most efficient solution for very large text inputs.
**Cons:** The logic can be slightly more complex to handle the state (`currentWordIsBroken`) and the word boundaries correctly, especially the last word.
### Explanation
The key insight here is that we don't need to store all the words at once. We can process the text character by character, keeping track of the state of the *current* word. 

We start by creating our `isBroken` boolean array as in the previous approach. We then initialize our `count` and a flag, `currentWordIsBroken`, which tracks if the word we are currently scanning contains a broken letter. We iterate through the `text`. When we see a letter, we check if it's broken. If it is, we set `currentWordIsBroken` to `true`. Once a word is marked as broken, we don't need to check its subsequent characters. When we encounter a space (or the end of the entire string), it signals the end of a word. At this point, we check our flag. If `currentWordIsBroken` is `false`, we increment our `count`. We then reset the flag to `false` to begin processing the next word. This method processes the entire text in one go, using only constant extra space for the lookup table and state flag.

```java
public int canBeTypedWords(String text, String brokenLetters) {
    boolean[] isBroken = new boolean[26];
    for (char c : brokenLetters.toCharArray()) {
        isBroken[c - 'a'] = true;
    }

    int count = 0;
    boolean currentWordIsBroken = false;
    for (int i = 0; i < text.length(); i++) {
        char c = text.charAt(i);
        if (c == ' ') {
            if (!currentWordIsBroken) {
                count++;
            }
            currentWordIsBroken = false; // Reset for the next word
        } else {
            if (isBroken[c - 'a']) {
                currentWordIsBroken = true;
            }
        }
    }

    // Check the last word after the loop finishes
    if (!currentWordIsBroken) {
        count++;
    }

    return count;
}
```
### Algorithm
- Create and populate a `boolean[26]` array `isBroken` from `brokenLetters`.
- Initialize `count = 0` and a flag `currentWordIsBroken = false`.
- Iterate through the `text` string character by character, including a conceptual character at the end.
- If the current character `c` is a space or we are at the end of the string:
  - This marks the end of a word.
  - If `currentWordIsBroken` is `false`, it means the word we just finished was typeable, so increment `count`.
  - Reset `currentWordIsBroken = false` for the next word.
- If the current character `c` is a letter:
  - Check if it's broken using the `isBroken` array (`isBroken[c - 'a']`).
  - If it is, set `currentWordIsBroken = true`.
- After the loop, return `count`.

# Solutions
### Java

```java
class Solution {
public
  int canBeTypedWords(String text, String brokenLetters) {
    boolean[] s = new boolean[26];
    for (char c : brokenLetters.toCharArray()) {
      s[c - 'a'] = true;
    }
    int ans = 0;
    for (String w : text.split(" ")) {
      for (char c : w.toCharArray()) {
        if (s[c - 'a']) {
          --ans;
          break;
        }
      }
      ++ans;
    }
    return ans;
  }
}

```

### Python

```python
class Solution:
    def canBeTypedWords(self, text: str, brokenLetters: str) -> int: s = set(brokenLetters) return sum(all(c not in s for c in w) for w in text . split())

```

### CPP

```cpp
class Solution {
public:
  int canBeTypedWords(string text, string brokenLetters) {
    bool s[26]{};
    for (char &c : brokenLetters) {
      s[c - 'a'] = true;
    }
    int ans = 0;
    for (auto &w : split(text, ' ')) {
      for (char &c : w) {
        if (s[c - 'a']) {
          --ans;
          break;
        }
      }
      ++ans;
    }
    return ans;
  }
  vector<string> split(const string &s, char c) {
    vector<string> ans;
    string t;
    for (char d : s) {
      if (d == c) {
        ans.push_back(t);
        t.clear();
      } else {
        t.push_back(d);
      }
    }
    ans.push_back(t);
    return ans;
  }
};

```