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 <= 1040 <= brokenLetters.length <= 26text consists of words separated by a single space without any leading or trailing spaces.brokenLetters consists of distinct lowercase English letters.In this approach, we will iterate over each word in the text and check if any of its characters are in the brokenLetters string. If a word does not contain any broken letters, it will be considered typeable, and we increment our count. This approach leverages the distinct nature of broken letters, allowing us to efficiently check inclusion using a set data structure.
The C language solution uses the strtok function to split the input text into words. It checks each character of a word against the brokenLetters using strchr. If none of the broken letters are in the word, the word is counted as typeable.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * m), where n is the number of characters in the text and m is the number of broken letters. Space Complexity: O(1), since we only maintain a few additional variables.
This approach relies on using set operations to determine each word's typeability efficiently. By converting the text and broken letters into sets, we can directly determine if a word includes any broken letters using intersection operations.
Python's set capabilities allow us to efficiently determine if any of the broken letters appear in each word by using the intersection operator `&`. If the intersection is empty, the word can be typed.
JavaScript
Time Complexity: O(n + m), where n is the total number of characters in the text, and m is the number of broken letters. Space Complexity: O(m) for storing broken letters as a set.
| Approach | Complexity |
|---|---|
| Approach 1: Checking Each Word for Broken Letters | Time Complexity: O(n * m), where n is the number of characters in the text and m is the number of broken letters. Space Complexity: O(1), since we only maintain a few additional variables. |
| Approach 2: Set Intersection to Determine Typeable Words | Time Complexity: O(n + m), where n is the total number of characters in the text, and m is the number of broken letters. Space Complexity: O(m) for storing broken letters as a set. |
Maximum Number of Balloons - Leetcode 1189 - Python • NeetCode • 25,417 views views
Watch 9 more video solutions →Practice Maximum Number of Words You Can Type with our built-in code editor and test cases.
Practice on FleetCode