We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Words You Can Type

Number: 1264

Difficulty: Easy

Paid? No

Companies: Quora

Problem Description

Given a string text containing words separated by a single space and a string brokenLetters representing distinct letters that are not working on a keyboard, determine the number of words from text that can be typed completely without using any of the brokenLetters.

Key Insights

  • Use a set to store the broken letters for efficient lookup.
  • Split the input text into words using the space delimiter.
  • For each word, check if it contains any letter from the broken set.
  • Count the words that do not include any broken letter.

Space and Time Complexity

Time Complexity: O(n) where n is the total number of characters in text.
Space Complexity: O(b) where b is the number of broken letters, which is bounded by 26.

Solution

We iterate through each word in the provided text and determine if the word can be typed using the keyboard by checking if any of its letters are present in the set of broken letters. If none of the letters are broken, we increment our count. We use a set data structure for the broken letters which provides O(1) lookup time, making our solution efficient.

Code Solutions

# Function to count the number of words that can be fully typed
def canBeTypedWords(text, brokenLetters):
    # Convert brokenLetters to a set for O(1) lookups
    broken_set = set(brokenLetters)
    # Split the text into words separated by space
    words = text.split(" ")
    count = 0
    # Iterate over each word
    for word in words:
        # Check if any character in the word is in the broken set
        can_type = True
        for letter in word:
            if letter in broken_set:
                can_type = False
                break
        # Increment count if the word can be fully typed
        if can_type:
            count += 1
    return count

# Example usage:
# print(canBeTypedWords("hello world", "ad"))  # Output: 1
← Back to All Questions