LeetCode #500 - Keyboard Row

📝 Introduction

Given an array of strings, return the words that can be typed using letters of the alphabet on only one row of a standard American keyboard.

The keyboard rows are: Top row: qwertyuiop Middle row: asdfghjkl Bottom row: zxcvbnm

You may return the answer in any order.

💡 Approach & Key Insights

The main idea is to check for each word if all its characters belong to the same keyboard row. By converting each word to lowercase and then to a set, we can easily determine if its characters are a subset of any one row.

🛠️ Breakdown of Approaches

1️⃣ Brute Force / Naive Approach

• Explanation: For each word, check if every character belongs to the same keyboard row by comparing each character to the characters in all three rows. This involves checking character-by-character for each word.
• Time Complexity: O(n * m) - where n is the number of words and m is the average length of each word.
• Space Complexity: O(1) - ignoring output space.
• Example/Dry Run:

1
Example input: ["Hello", "Alaska", "Dad", "Peace"]
2

3
"Hello" → uses letters from multiple rows → ✘
4
"Alaska" → only row 2 → ✔
5
"Dad" → only row 2 → ✔
6
"Peace" → multiple rows → ✘
7

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

2️⃣ Optimized Approach

• Explanation: Instead of checking characters one by one, convert each row into a set. Then convert the word into a lowercase set and check if it’s a subset of any of the three row sets.
• Time Complexity: O(n * m) - where n is the number of words and m is the average length of the words. Checking issubset is efficient for set comparisons.
• Space Complexity: O(1) - excluding the space for the output list.
• Example/Dry Run:

1
Example input: ["Hello", "Alaska", "Dad", "Peace"]
2

3
Step 1 → Convert keyboard rows into sets
4
Step 2 → For each word, convert to lowercase set
5
Step 3 → Check if set is subset of row1, row2, or row3
6

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

3️⃣ Best / Final Optimized Approach (if applicable)

• Explanation: The current solution is optimal for this problem. Using sets makes subset checking straightforward and efficient.
• Time Complexity: O(n * m)
• Space Complexity: O(1)
• Example/Dry Run:

1
Input: ["Type", "Row", "Zzz"]
2

3
"Type" → mixed rows → ✘
4
"Row" → row 1 → ✔
5
"Zzz" → row 3 → ✔
6

7
Output: ["Row", "Zzz"]

📊 Complexity Analysis

📉 Optimization Ideas

You could pre-map each letter to its row number and then verify if all characters in a word belong to the same row number. This might slightly improve runtime in practice, but the set-based method is already clean and efficient.

📌 Example Walkthroughs & Dry Runs

1
Example:
2
Input: ["Alaska", "Dad", "Peace"]
3

4
Process:
5
1. Alaska → to lower → "alaska" → set("alaska") = {'a', 'l', 's', 'k'} ⊆ row2 → ✔
6
2. Dad → "dad" → {'d', 'a'} ⊆ row2 → ✔
7
3. Peace → "peace" → {'p', 'e', 'a', 'c'} ⊄ any row → ✘
8

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

🔗 Additional Resources

• Resource 1
• Resource 2
• Resource 3

Author: Daniel Nallapalli Date: 16/06/2025