Problem Description

You are given an array of strings words. Your task is to find and return all words that can be typed using letters from only one row of an American keyboard.

The American keyboard has three rows of letter keys:

• First row: "qwertyuiop"
• Second row: "asdfghjkl"
• Third row: "zxcvbnm"

A word can be typed using only one row if all the letters in that word (regardless of case) belong to the same keyboard row. The comparison is case-insensitive, meaning uppercase and lowercase versions of the same letter are considered to be on the same row.

For example:

• The word "Hello" cannot be typed using one row because 'h' is on the second row, 'e' is on the first row, and 'l' and 'o' are on different rows
• The word "Alaska" can be typed using only the second row because all its letters ('a', 'l', 's', 'k') are found on the second row
• The word "Dad" can be typed using only the second row because both 'd' and 'a' are on the second row

The solution approach creates three sets containing the letters from each keyboard row. For each word in the input array, it converts the word to lowercase and creates a set of its characters. If this character set is a subset of any of the three row sets (checked using the <= operator), it means all letters of the word belong to that single row, so the word is added to the result list.

Intuition

The key insight is recognizing this as a set membership problem. When we need to check if a word can be typed using only one keyboard row, we're essentially asking: "Do all letters in this word belong to the same row?"

This naturally leads us to think about sets. Each keyboard row can be represented as a set of characters. For any given word, if we convert it to a set of characters, we can check whether this word's character set is completely contained within one of the row sets.

The mathematical relationship we're looking for is the subset relationship. If word_characters ⊆ row_characters, then all letters in the word exist in that row. In Python, this subset check is elegantly expressed using the <= operator between sets.

Why convert the word to lowercase? Since the problem states that typing is case-insensitive (both 'A' and 'a' are on the same key), we normalize everything to lowercase to simplify our comparison. This way, we don't need to store both uppercase and lowercase versions of each letter in our row sets.

The beauty of this approach is its simplicity - we transform the problem from "checking each character's row and ensuring they're all the same" to "checking if a word's character set is a subset of any row set". This reduces what could be a complex character-by-character validation into three simple subset checks using s <= s1 or s <= s2 or s <= s3.

Solution Approach

The implementation follows a straightforward set-based approach:

1. Initialize Row Sets

s1 = set('qwertyuiop')
s2 = set('asdfghjkl')
s3 = set('zxcvbnm')

We create three sets, each containing the characters from one keyboard row. Using sets gives us O(1) lookup time for membership checking and built-in subset operations.

2. Process Each Word

ans = []
for w in words:

We initialize an empty result list and iterate through each word in the input array.

3. Normalize and Convert to Set

s = set(w.lower())

For each word, we:

• Convert it to lowercase to handle case-insensitivity
• Transform it into a set of characters, which automatically removes duplicates and prepares it for subset comparison

4. Check Subset Relationship

if s <= s1 or s <= s2 or s <= s3:
    ans.append(w)

The <= operator in Python checks if the left set is a subset of the right set. If the word's character set is a subset of any row set, it means all letters in the word come from that single row. When this condition is true, we add the original word (preserving its original case) to our answer list.

5. Return Results

return ans

After processing all words, we return the list of words that can be typed using only one keyboard row.

Time Complexity: O(n × m) where n is the number of words and m is the average length of each word (for converting to set)
Space Complexity: O(1) for the row sets (constant size) plus O(k) for the answer list where k is the number of valid words

Example Walkthrough

Let's walk through the solution with the input: words = ["Hello", "Alaska", "Dad", "Peace"]

Step 1: Initialize keyboard row sets

• s1 = {'q','w','e','r','t','y','u','i','o','p'}
• s2 = {'a','s','d','f','g','h','j','k','l'}
• s3 = {'z','x','c','v','b','n','m'}

Step 2: Process each word

Word 1: "Hello"

• Convert to lowercase: "hello"
• Create character set: s = {'h','e','l','o'}
• Check subsets:
  • Is {'h','e','l','o'} ⊆ s1? No (h is not in row 1)
  • Is {'h','e','l','o'} ⊆ s2? No (e and o are not in row 2)
  • Is {'h','e','l','o'} ⊆ s3? No (h, e, l, o are not in row 3)
• Result: Not added to answer

Word 2: "Alaska"

• Convert to lowercase: "alaska"
• Create character set: s = {'a','l','s','k'}
• Check subsets:
  • Is {'a','l','s','k'} ⊆ s1? No (none of these are in row 1)
  • Is {'a','l','s','k'} ⊆ s2? Yes! All letters are in row 2
• Result: "Alaska" added to answer

Word 3: "Dad"

• Convert to lowercase: "dad"
• Create character set: s = {'d','a'}
• Check subsets:
  • Is {'d','a'} ⊆ s1? No
  • Is {'d','a'} ⊆ s2? Yes! Both letters are in row 2
• Result: "Dad" added to answer

Word 4: "Peace"

• Convert to lowercase: "peace"
• Create character set: s = {'p','e','a','c'}
• Check subsets:
  • Is {'p','e','a','c'} ⊆ s1? No (a and c are not in row 1)
  • Is {'p','e','a','c'} ⊆ s2? No (p, e, c are not in row 2)
  • Is {'p','e','a','c'} ⊆ s3? No (p, e, a are not in row 3)
• Result: Not added to answer

Final Output: ["Alaska", "Dad"]

Solution Implementation

Time and Space Complexity

Time Complexity: O(n * m) where n is the number of words in the input list and m is the average length of each word.

• Creating the three sets s1, s2, s3 takes O(1) time since they contain a fixed number of characters
• The main loop iterates through all n words
• For each word:
  • Converting to lowercase takes O(m) time where m is the length of the word
  • Creating a set from the lowercase word takes O(m) time
  • The subset check (<=) operation takes O(len(s)) time, which is at most O(m) since s contains unique characters from the word
  • Appending to the answer list takes O(1) amortized time
• Overall: O(n * m)

Space Complexity: O(n * m) in the worst case

• The three keyboard row sets s1, s2, s3 use O(1) space (fixed size)
• For each word, we create a temporary set s which uses O(m) space where m is the length of the word
• The answer list ans can contain at most n words, and storing these words requires O(n * m) space in total
• Overall: O(n * m) dominated by the space needed to store the output

Common Pitfalls

1. Forgetting Case-Insensitive Comparison

One of the most common mistakes is forgetting to handle uppercase letters properly. The keyboard row sets only contain lowercase letters, so comparing uppercase letters directly will fail.

Incorrect Code:

def findWords(self, words: List[str]) -> List[str]:
    first_row = set('qwertyuiop')
    second_row = set('asdfghjkl')
    third_row = set('zxcvbnm')
    result = []
  
    for word in words:
        # WRONG: Not converting to lowercase
        word_chars = set(word)  # This will fail for words like "Alaska"
      
        if (word_chars <= first_row or 
            word_chars <= second_row or 
            word_chars <= third_row):
            result.append(word)
  
    return result

Why it fails: The word "Alaska" contains uppercase 'A' which won't match lowercase 'a' in the row sets, causing valid words to be incorrectly rejected.

Solution: Always convert the word to lowercase before creating the character set:

word_chars = set(word.lower())  # Correct approach

2. Modifying the Original Word Instead of Preserving Case

Another pitfall is returning the lowercase version of the word instead of preserving the original casing.

Incorrect Code:

def findWords(self, words: List[str]) -> List[str]:
    first_row = set('qwertyuiop')
    second_row = set('asdfghjkl')
    third_row = set('zxcvbnm')
    result = []
  
    for word in words:
        word_lower = word.lower()  # Store lowercase version
        word_chars = set(word_lower)
      
        if (word_chars <= first_row or 
            word_chars <= second_row or 
            word_chars <= third_row):
            result.append(word_lower)  # WRONG: Appending lowercase version
  
    return result

Why it fails: The problem requires returning words in their original form. If the input is ["Hello", "Alaska"], we should return ["Alaska"], not ["alaska"].

Solution: Always append the original word to the result:

result.append(word)  # Preserve original casing

3. Using Incorrect Set Operations

Some might try to use intersection or other set operations incorrectly instead of the subset check.

Incorrect Code:

# WRONG: Checking if there's ANY overlap, not if ALL characters are in the row
if word_chars & first_row:  # This checks for any intersection
    result.append(word)

Why it fails: The intersection operator & returns a non-empty set if there's any overlap. The word "Hello" would incorrectly pass for the first row because 'e' and 'o' are in the first row, even though 'h' and 'l' are not.

Solution: Use the subset operator <= to ensure ALL characters are in the same row:

if word_chars <= first_row:  # Correct: checks if word_chars is a subset