1935. Maximum Number of Words You Can Type

Description

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.

Solutions

Solution 1: Array or Hash Table

Thinking

A word is typable iff it contains no broken letter. Put broken letters in a set and split \(\textit{text}\) on spaces.

Count words whose every character misses the set. The alphabet is constant, so the pass is linear in the text length.

We can use a hash table or an array \(s\) of length \(26\) to record all the broken letter keys.

Then, we traverse each word \(w\) in the string \(text\), and if any letter \(c\) in \(w\) appears in \(s\), it means that the word cannot be typed, and we do not need to add one to the answer. Otherwise, we need to add one to the answer.

After the traversal, we return the answer.

Python3JavaC++GoTypeScriptRustC#

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())

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;
    }
}

class Solution {
public:
    int canBeTypedWords(string text, string brokenLetters) {
        bool s[26]{};
        for (char c : brokenLetters) {
            s[c - 'a'] = true;
        }
        int ans = 0;
        stringstream ss(text);
        string w;
        while (ss >> w) {
            for (char c : w) {
                if (s[c - 'a']) {
                    --ans;
                    break;
                }
            }
            ++ans;
        }
        return ans;
    }
};

func canBeTypedWords(text string, brokenLetters string) (ans int) {
    s := [26]bool{}
    for _, c := range brokenLetters {
        s[c-'a'] = true
    }
    for _, w := range strings.Split(text, " ") {
        for _, c := range w {
            if s[c-'a'] {
                ans--
                break
            }
        }
        ans++
    }
    return
}

function canBeTypedWords(text: string, brokenLetters: string): number {
    const s: boolean[] = Array(26).fill(false);
    for (const c of brokenLetters) {
        s[c.charCodeAt(0) - 'a'.charCodeAt(0)] = true;
    }
    let ans = 0;
    for (const w of text.split(' ')) {
        for (const c of w) {
            if (s[c.charCodeAt(0) - 'a'.charCodeAt(0)]) {
                --ans;
                break;
            }
        }
        ++ans;
    }
    return ans;
}

impl Solution {
    pub fn can_be_typed_words(text: String, broken_letters: String) -> i32 {
        let mut s = vec![false; 26];
        for c in broken_letters.chars() {
            s[(c as usize) - ('a' as usize)] = true;
        }
        let mut ans = 0;
        let words = text.split_whitespace();
        for w in words {
            for c in w.chars() {
                if s[(c as usize) - ('a' as usize)] {
                    ans -= 1;
                    break;
                }
            }
            ans += 1;
        }
        ans
    }
}

public class Solution {
    public int CanBeTypedWords(string text, string brokenLetters) {
        bool[] s = new bool[26];
        foreach (char c in brokenLetters) {
            s[c - 'a'] = true;
        }
        int ans = 0;
        string[] words = text.Split(' ');
        foreach (string w in words) {
            foreach (char c in w) {
                if (s[c - 'a']) {
                    --ans;
                    break;
                }
            }
            ++ans;
        }
        return ans;
    }
}

1935. Maximum Number of Words You Can Type

Description

Solutions

Solution 1: Array or Hash Table

Comments