algoadvance

Given a text string and a string containing broken letters (characters that cannot be pressed), your task is to determine the maximum number of words in the text that can be typed using the remaining non-broken letters. Each word in the text is separated by a single space.

Example:

• Input: text = “hello world”, brokenLetters = “ad”
• Output: 1
• Explanation: Only “world” can be typed out, because “hello” contains the broken letter “d”.

Clarifying Questions

1. Q: Are all characters in the text lowercase letters?
   • A: Yes, you can assume all input text consists of lowercase English letters and spaces.
2. Q: Can brokenLetters be an empty string?
   • A: Yes, if brokenLetters is an empty string, it means no keys are broken.
3. Q: Can there be multiple spaces between words in the text?
   • A: No, words in the text are separated by single spaces only.
4. Q: What is the maximum length of the text and the brokenLetters?
   • A: The length of the text and brokenLetters will be within reasonable limits (Not provided, but assume typical problem constraints like < 10^4).

Strategy

1. Split the Text:
   • Use the split() method to break the text into individual words.
2. Check Each Word:
   • For each word, check if any character in the word is in the set of broken letters.
3. Count Typable Words:
   • If a word can be typed (i.e., no characters in the word are broken), add to a counter.
4. Return the Count:
   • Return the final count of words that can be typed.

Time Complexity

The time complexity is O(N * M), where N is the number of words in the text and M is the average length of a word. The split() method and iterating over each character of each word contributes to this complexity.

Code

def canBeTypedWords(text, brokenLetters):
    broken_set = set(brokenLetters)  # Create a set of broken letters for quick lookup
    words = text.split()  # Split the text into individual words
    
    typable_count = 0
    
    for word in words:
        # Check if the word contains any broken letter
        if all(char not in broken_set for char in word):
            typable_count += 1
    
    return typable_count

# Example usage:
text = "hello world"
brokenLetters = "ad"
print(canBeTypedWords(text, brokenLetters))  # Output should be 1

Explanation:

• broken_set: A set containing the broken letters for fast membership checking.
• words: A list obtained by splitting the input text by spaces.
• typable_count: A counter to keep track of how many words can be typed without using broken letters.
• if all(char not in broken_set for char in word): This condition checks if all characters in a word are not in the set of broken letters.

Try our interview co-pilot at AlgoAdvance.com

• 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?