LeetCode 500: Keyboard Row

Problem Restatement

We are given an array of strings words.

Return the words that can be typed using letters from only one row of an American keyboard.

The keyboard rows are:

Row	Letters
First row	qwertyuiop
Second row	asdfghjkl
Third row	zxcvbnm

Letter case does not matter. For example, A and a belong to the same row. The word must use letters from only one row. The original word should be returned with its original casing.

Input and Output

Item	Meaning
Input	Array of strings words
Output	Words that can be typed using one keyboard row
Case rule	Case-insensitive check
Return rule	Keep original word casing

Function shape:

def findWords(words: list[str]) -> list[str]:
    ...

Examples

Example 1:

words = ["Hello", "Alaska", "Dad", "Peace"]

Check each word:

Word	Rows used	Valid
"Hello"	multiple rows	no
"Alaska"	second row only	yes
"Dad"	second row only	yes
"Peace"	multiple rows	no

Answer:

["Alaska", "Dad"]

Example 2:

words = ["omk"]

The letters are not all from one row.

Answer:

[]

Example 3:

words = ["adsdf", "sfd"]

Both words use only the second row.

Answer:

["adsdf", "sfd"]

First Thought: Check Each Row

For each word, we can check whether all its letters are in one of the three keyboard rows.

Represent each row as a set:

set("qwertyuiop")
set("asdfghjkl")
set("zxcvbnm")

Then convert the word to lowercase and check membership.

Key Insight

A word is valid if the set of its lowercase letters is a subset of one keyboard row.

For example:

word = "Alaska"
letters = set(word.lower())

The set is:

{"a", "l", "s", "k"}

All of these letters are in:

set("asdfghjkl")

So "Alaska" is valid.

For "Hello":

{"h", "e", "l", "o"}

These letters are split across rows, so it is invalid.

Algorithm

Create three sets, one for each keyboard row.

For each word:

1. Convert it to lowercase.
2. Convert its letters to a set.
3. Check whether this set is a subset of any keyboard row.
4. If yes, append the original word to the answer.

Return the answer.

Correctness

The algorithm checks each word after converting it to lowercase, so uppercase and lowercase letters are treated the same.

For a word to be typed using one row, every distinct letter in that word must belong to the same row. Converting the word to a set of letters captures exactly the distinct letters used by the word.

If this letter set is a subset of one keyboard row set, then every letter in the word can be typed from that row, so the word is valid.

If the letter set is not a subset of any row, then the word uses letters from at least two rows, so it cannot be typed using one row.

Therefore, the algorithm returns exactly the valid words.

Complexity

Let:

Symbol	Meaning
n	number of words
L	total number of characters across all words

Metric	Value	Why
Time	O(L)	Each character is processed a constant number of times
Space	O(1) excluding output	Keyboard row sets have fixed size

Implementation

class Solution:
    def findWords(self, words: list[str]) -> list[str]:
        rows = [
            set("qwertyuiop"),
            set("asdfghjkl"),
            set("zxcvbnm"),
        ]

        ans = []

        for word in words:
            letters = set(word.lower())

            if any(letters <= row for row in rows):
                ans.append(word)

        return ans

Code Explanation

The keyboard rows are stored as sets:

rows = [
    set("qwertyuiop"),
    set("asdfghjkl"),
    set("zxcvbnm"),
]

For each word, convert it to lowercase and collect its letters:

letters = set(word.lower())

This checks whether all letters come from one row:

if any(letters <= row for row in rows):

The operator <= means “is subset of” for sets.

If the word is valid, append the original word:

ans.append(word)

Testing

def run_tests():
    s = Solution()

    assert s.findWords(["Hello", "Alaska", "Dad", "Peace"]) == ["Alaska", "Dad"]
    assert s.findWords(["omk"]) == []
    assert s.findWords(["adsdf", "sfd"]) == ["adsdf", "sfd"]
    assert s.findWords(["TYPE", "row"]) == ["TYPE", "row"]
    assert s.findWords(["a", "S", "z"]) == ["a", "S", "z"]

    print("all tests passed")

run_tests()

Test meaning:

Test	Why
["Hello", "Alaska", "Dad", "Peace"]	Main example
["omk"]	Invalid mixed-row word
["adsdf", "sfd"]	All valid second-row words
["TYPE", "row"]	Case-insensitive checking
Single-letter words	Any single letter is valid