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 thenumber of words in text you can fully type using this keyboard.

Examples

Example 1

1
2
3

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

Example 2

1
2
3

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

Example 3

1
2
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^4
  • 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.

Solution

Method 1 – Set Lookup for Broken Letters

Intuition

A word can be typed if none of its letters are in the set of broken letters. We can use a set for fast lookup and check each word in the text.

Approach

  1. Convert brokenLetters to a set for O(1) lookup.
  2. Split the text into words.
  3. For each word, check if any character is in the broken set.
  4. Count the words that do not contain any broken letter.
  5. Return the count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    int canBeTypedWords(string text, string brokenLetters) {
        unordered_set<char> broken(brokenLetters.begin(), brokenLetters.end());
        int ans = 0;
        istringstream iss(text);
        string word;
        while (iss >> word) {
            bool ok = true;
            for (char c : word) if (broken.count(c)) { ok = false; break; }
            if (ok) ans++;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func canBeTypedWords(text string, brokenLetters string) int {
    broken := map[rune]bool{}
    for _, c := range brokenLetters {
        broken[c] = true
    }
    ans := 0
    for _, word := range strings.Fields(text) {
        ok := true
        for _, c := range word {
            if broken[c] {
                ok = false
                break
            }
        }
        if ok {
            ans++
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public int canBeTypedWords(String text, String brokenLetters) {
        Set<Character> broken = new HashSet<>();
        for (char c : brokenLetters.toCharArray()) broken.add(c);
        int ans = 0;
        for (String word : text.split(" ")) {
            boolean ok = true;
            for (char c : word.toCharArray()) if (broken.contains(c)) { ok = false; break; }
            if (ok) ans++;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    fun canBeTypedWords(text: String, brokenLetters: String): Int {
        val broken = brokenLetters.toSet()
        var ans = 0
        for (word in text.split(" ")) {
            if (word.all { it !in broken }) ans++
        }
        return ans
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def canBeTypedWords(self, text: str, brokenLetters: str) -> int:
        broken = set(brokenLetters)
        ans = 0
        for word in text.split():
            if all(c not in broken for c in word):
                ans += 1
        return ans
1
2
3
4
5
6

impl Solution {
    pub fn can_be_typed_words(text: String, broken_letters: String) -> i32 {
        let broken: std::collections::HashSet<char> = broken_letters.chars().collect();
        text.split_whitespace().filter(|w| w.chars().all(|c| !broken.contains(&c))).count() as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    canBeTypedWords(text: string, brokenLetters: string): number {
        const broken = new Set(brokenLetters)
        let ans = 0
        for (const word of text.split(' ')) {
            if ([...word].every(c => !broken.has(c))) ans++
        }
        return ans
    }
}

Complexity

  • ⏰ Time complexity: O(n) — Where n is the total number of characters in text and brokenLetters.
  • 🧺 Space complexity: O(1) — The set of broken letters is at most 26.