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

Keyboard Row

Number: 500

Difficulty: Easy

Paid? No

Companies: Google, Microsoft, Amazon, MathWorks

Problem Description

Given an array of words, return the words that can be typed using letters of the alphabet on only one row of an American keyboard. The solution must be case-insensitive, meaning both uppercase and lowercase representations of a letter are considered equivalent. The American keyboard layout has three rows: the first row is "qwertyuiop", the second row is "asdfghjkl", and the third row is "zxcvbnm".

Key Insights

  • Convert each word to a consistent case (lowercase) for uniform processing.
  • Predefine sets for the three keyboard rows.
  • For each word, determine if all its characters belong to a single keyboard row by checking if the set of characters is a subset of one of the row sets.
  • Use set operations for an efficient subset check.

Space and Time Complexity

Time Complexity: O(n * m) where n is the number of words and m is the maximum length of a word, since each word's characters are checked. Space Complexity: O(1) in terms of extra space aside from the output list, as the keyboard row sets require constant space.

Solution

The algorithm works by first creating three sets representing the letters in each row of the American keyboard. Then, for each word in the input, we convert it to lowercase and create a set of its characters. By checking if this set is a subset of any one of the three row sets, we can decide whether the word can be typed using only one row. If the condition is met, the word is added to the result list.

Code Solutions

# Define the function to solve the problem
def findWords(words):
    # Define sets for each row of the American keyboard
    row1 = set("qwertyuiop")
    row2 = set("asdfghjkl")
    row3 = set("zxcvbnm")
    
    valid_words = []  # List to store words that match the condition
    
    # Iterate over each word in the input list
    for word in words:
        # Convert word to lowercase for case-insensitive comparison
        lower_word = word.lower()
        # Create a set of characters from the word for efficient lookup
        letters = set(lower_word)
        # Check if the letters belong to any one of the keyboard rows
        if letters <= row1 or letters <= row2 or letters <= row3:
            valid_words.append(word)
    
    return valid_words

# Example usage:
words = ["Hello", "Alaska", "Dad", "Peace"]
print(findWords(words))  # Output: ["Alaska", "Dad"]
← Back to All Questions