LeetCode 500 - Keyboard Row

Difficulty: 🟢 Easy
Topics: Array, Hash Table, String

Solution

Problem Understanding

This problem asks us to determine which words in a given list can be typed using letters from only one row of an American keyboard.

The input is an array of strings, words, where each string represents a word consisting only of English alphabet characters. The task is to return only those words where every character belongs to the same keyboard row. The keyboard has three rows:

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

The problem is case-insensitive, meaning uppercase and lowercase versions of the same character are treated identically. For example, 'A' and 'a' belong to the same row.

To understand the expected output, consider the word "Alaska". After ignoring case, all letters belong to the second row, so it should be included in the result. However, "Hello" uses letters from multiple rows, so it should not be included.

The constraints are small:

At most 20 words
Each word length is at most 100 characters

This tells us performance is not a major concern, and even a straightforward approach will run comfortably within limits. However, we still want a clean and efficient implementation.

There are several edge cases worth identifying upfront. Words may contain a mix of uppercase and lowercase letters, so a case-sensitive implementation would fail unless normalization is performed. Single-character words should always qualify because one character necessarily belongs to a single row. Words that begin with one row but later contain a character from another row must be rejected. The problem guarantees that all characters are English letters, meaning we do not need to handle numbers, spaces, or symbols.

Approaches

Brute Force Approach

A brute-force solution would compare every character of a word against all three keyboard rows repeatedly.

For each word, we could check every row individually and determine whether all characters belong to that row. This means:

Convert the word to lowercase.
For each keyboard row:

Check whether every character exists in that row.

If any row fully matches, add the word to the result.

This approach is correct because it explicitly tests every possible keyboard row. If all characters fit into one row, the word qualifies.

However, membership checking inside a string is relatively inefficient because searching for a character inside a row string takes linear time. Since we repeatedly scan row strings for each character, unnecessary repeated work occurs.

Although the constraints are small enough that this would still pass, we can improve the lookup efficiency.

Optimal Approach

The key observation is that every letter always belongs to exactly one keyboard row. Instead of repeatedly searching row strings, we can precompute a mapping from character to row number.

For example:

'q' → 1
'a' → 2
'z' → 3

Once this mapping exists, checking a word becomes simple:

Convert the word to lowercase.
Find the row of the first character.
Ensure every remaining character belongs to the same row.
If they all match, include the word in the result.

A hash table (dictionary in Python, map in Go) makes row lookup constant time, which simplifies the implementation and avoids repeated scanning.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × m × r)	O(1)	For each word and character, repeatedly checks row membership, where `r = 3` keyboard rows
Optimal	O(n × m)	O(1)	Uses a hash table for constant-time row lookup

Here:

n = number of words
m = average word length

Since the keyboard has only 26 letters, the extra space remains constant.

Algorithm Walkthrough

Create a hash table that maps every lowercase character to its keyboard row number.

This preprocessing step allows constant-time row lookup for every letter. Instead of repeatedly searching strings like "qwertyuiop", we immediately know which row a character belongs to. 2. Initialize an empty result list.

This list will store words that satisfy the one-row condition. 3. Iterate through each word in words.

Each word must be checked independently. 4. Convert the current word to lowercase.

Since the problem is case-insensitive, normalizing case ensures consistent row lookups. 5. Determine the keyboard row of the first character.

The first letter establishes the row that every other character must match. 6. Iterate through the remaining characters in the word.

For each character:

Look up its row using the hash table.
Compare it to the first character’s row.

If any character belongs to a different row, stop checking the current word.

The word immediately becomes invalid because it uses multiple keyboard rows. 8. If all characters match the same row, add the original word to the result.

We return the original casing, not the lowercase version. 9. Return the result list after processing all words.

Why it works

The algorithm maintains a simple invariant: every processed character in the current word must belong to the same keyboard row as the first character. Since every English letter belongs to exactly one keyboard row, the moment we find a mismatch, the word cannot qualify. If no mismatch exists after checking all characters, then every character belongs to the same row, proving the word is valid.

Python Solution

from typing import List

class Solution:
    def findWords(self, words: List[str]) -> List[str]:
        keyboard_row = {}

        for char in "qwertyuiop":
            keyboard_row[char] = 1

        for char in "asdfghjkl":
            keyboard_row[char] = 2

        for char in "zxcvbnm":
            keyboard_row[char] = 3

        valid_words = []

        for word in words:
            lowercase_word = word.lower()
            target_row = keyboard_row[lowercase_word[0]]

            can_type = True

            for char in lowercase_word:
                if keyboard_row[char] != target_row:
                    can_type = False
                    break

            if can_type:
                valid_words.append(word)

        return valid_words

The implementation begins by constructing a dictionary that maps every letter to its keyboard row number. This preprocessing step eliminates repeated row scanning and gives us constant-time lookups.

Next, we iterate through every word. Since uppercase and lowercase letters should be treated identically, the word is converted to lowercase before processing.

The first character determines the target row. Every remaining character is compared against that row using the dictionary lookup. If any mismatch occurs, we immediately stop checking the word because it cannot satisfy the requirement.

If all characters match the same row, the original word is added to the result list. Returning the original word preserves its casing, which matches the expected output.

Go Solution

func findWords(words []string) []string {
	keyboardRow := make(map[rune]int)

	for _, char := range "qwertyuiop" {
		keyboardRow[char] = 1
	}

	for _, char := range "asdfghjkl" {
		keyboardRow[char] = 2
	}

	for _, char := range "zxcvbnm" {
		keyboardRow[char] = 3
	}

	result := []string{}

	for _, word := range words {
		lowercaseWord := []rune(strings.ToLower(word))
		targetRow := keyboardRow[lowercaseWord[0]]

		canType := true

		for _, char := range lowercaseWord {
			if keyboardRow[char] != targetRow {
				canType = false
				break
			}
		}

		if canType {
			result = append(result, word)
		}
	}

	return result
}

The Go solution follows the same logic as the Python version, but there are a few implementation differences.

Go uses a map[rune]int instead of a Python dictionary. Since strings in Go are UTF-8 encoded, iterating over characters uses rune. The word is converted to lowercase using strings.ToLower().

Unlike Python lists, Go slices are used for the result collection. Appending qualifying words is done using append().

One important detail is that this solution requires importing the strings package:

import "strings"

No special handling for nil versus empty slices is required because an empty slice naturally represents an empty result.

Worked Examples

Example 1

Input: ["Hello","Alaska","Dad","Peace"]

We first build the keyboard row mapping.

Character	Row
q, w, e, r, t, y, u, i, o, p	1
a, s, d, f, g, h, j, k, l	2
z, x, c, v, b, n, m	3

Processing `"Hello"`

Lowercase: "hello"

Character	Row	Matches Target Row?
h	2	Yes
e	1	No
l	2	Not checked
l	2	Not checked
o	1	Not checked

Since 'e' belongs to a different row, "Hello" is rejected.

Processing `"Alaska"`

Lowercase: "alaska"

Target row = 2

Character	Row	Matches Target Row?
a	2	Yes
l	2	Yes
a	2	Yes
s	2	Yes
k	2	Yes
a	2	Yes

All characters match, so "Alaska" is added.

Processing `"Dad"`

Lowercase: "dad"

Target row = 2

Character	Row	Matches Target Row?
d	2	Yes
a	2	Yes
d	2	Yes

All characters match, so "Dad" is added.

Processing `"Peace"`

Lowercase: "peace"

Target row = 1

Character	Row	Matches Target Row?
p	1	Yes
e	1	Yes
a	2	No

The word is rejected.

Output: ["Alaska", "Dad"]

Example 2

Input: ["omk"]

Lowercase: "omk"

Target row = 1

Character	Row	Matches Target Row?
o	1	Yes
m	3	No
k	2	Not checked

Mismatch occurs, so the word is rejected.

Output: []

Example 3

Input: ["adsdf","sfd"]

Processing `"adsdf"`

Target row = 2

Character	Row	Matches Target Row?
a	2	Yes
d	2	Yes
s	2	Yes
d	2	Yes
f	2	Yes

Valid word.

Processing `"sfd"`

Target row = 2

Character	Row	Matches Target Row?
s	2	Yes
f	2	Yes
d	2	Yes

Valid word.

Output: ["adsdf", "sfd"]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n × m)	Each character of each word is checked exactly once
Space	O(1)	The keyboard mapping has fixed size, 26 letters

The algorithm processes every character in every word exactly one time. Since keyboard row lookup is constant time due to the hash table, the total work scales linearly with the total number of characters.

The auxiliary space remains constant because the keyboard mapping always contains only 26 entries, regardless of input size. The output list is not counted toward auxiliary space complexity.

Test Cases

solution = Solution()

assert solution.findWords(
    ["Hello", "Alaska", "Dad", "Peace"]
) == ["Alaska", "Dad"]  # provided example

assert solution.findWords(
    ["omk"]
) == []  # provided invalid example

assert solution.findWords(
    ["adsdf", "sfd"]
) == ["adsdf", "sfd"]  # provided valid example

assert solution.findWords(
    ["A"]
) == ["A"]  # single character word

assert solution.findWords(
    ["qwerty", "asdf", "zxcvb"]
) == ["qwerty", "asdf", "zxcvb"]  # one valid word per row

assert solution.findWords(
    ["Hello"]
) == []  # mixed keyboard rows

assert solution.findWords(
    ["Dad", "MOM"]
) == ["Dad"]  # uppercase handling and invalid mixed row

assert solution.findWords(
    ["aaa", "bbb", "ccc"]
) == ["aaa", "bbb", "ccc"]  # repeated same-row letters

assert solution.findWords(
    ["QwErTy"]
) == ["QwErTy"]  # mixed case but same row

assert solution.findWords(
    ["type", "sad", "zoo"]
) == ["sad"]  # multiple invalid words

Test	Why
`["Hello","Alaska","Dad","Peace"]`	Validates provided mixed example
`["omk"]`	Verifies rejection of mixed-row word
`["adsdf","sfd"]`	Verifies multiple valid outputs
`["A"]`	Tests minimum word length
`["qwerty","asdf","zxcvb"]`	Verifies all three rows work
`["Hello"]`	Confirms invalid mixed row detection
`["Dad","MOM"]`	Tests case insensitivity
`["aaa","bbb","ccc"]`	Verifies repeated characters
`["QwErTy"]`	Confirms mixed casing works
`["type","sad","zoo"]`	Tests filtering behavior

Edge Cases

Single Character Words

A one-character word always qualifies because a single letter necessarily belongs to exactly one keyboard row. A careless implementation might accidentally assume multiple characters exist and cause indexing issues. This implementation handles it naturally because the first character defines the row, and the validation loop succeeds immediately.

Mixed Uppercase and Lowercase Letters

Words such as "Dad" or "QwErTy" contain uppercase letters. A case-sensitive implementation would incorrectly treat uppercase letters as missing from the row mapping. This solution converts every word to lowercase before checking, ensuring correct row comparisons.

Early Mismatch in a Word

A word like "Hello" becomes invalid as soon as 'e' is encountered because it belongs to a different keyboard row than 'h'. A naive implementation might continue scanning unnecessarily. This solution stops immediately using break, avoiding extra work and improving efficiency.

LeetCode 500 - Keyboard Row

Solution

Problem Understanding

Approaches

Brute Force Approach

Optimal Approach

Algorithm Walkthrough

Why it works

Python Solution

Go Solution

Worked Examples

Example 1

Processing "Hello"

Processing "Alaska"

Processing "Dad"

Processing "Peace"

Example 2

Example 3

Processing "adsdf"

Processing "sfd"

Complexity Analysis

Test Cases

Edge Cases

Single Character Words

Mixed Uppercase and Lowercase Letters

Early Mismatch in a Word

Processing `"Hello"`

Processing `"Alaska"`

Processing `"Dad"`

Processing `"Peace"`

Processing `"adsdf"`

Processing `"sfd"`