Given an array of strings words, return the words that can be typed using letters of the alphabet on only one row of American keyboard like the image below.
Note that the strings are case-insensitive, both lowercased and uppercased of the same letter are treated as if they are at the same row.
In the American keyboard:
"qwertyuiop","asdfghjkl", and"zxcvbnm".
Example 1:
Input: words = ["Hello","Alaska","Dad","Peace"]
Output: ["Alaska","Dad"]
Explanation:
Both "a" and "A" are in the 2nd row of the American keyboard due to case insensitivity.
Example 2:
Input: words = ["omk"]
Output: []
Example 3:
Input: words = ["adsdf","sfd"]
Output: ["adsdf","sfd"]
Constraints:
1 <= words.length <= 201 <= words[i].length <= 100words[i] consists of English letters (both lowercase and uppercase). Problem Overview: You get a list of words and need to return only those that can be typed using letters from a single row of the American keyboard. The three rows are qwertyuiop, asdfghjkl, and zxcvbnm. For each word, verify that every character belongs to the same row.
Approach 1: Using Sets for Each Keyboard Row (O(N) time, O(1) space)
Create three set objects representing the keyboard rows. Iterate through each word in the input array. Convert the word to lowercase, then check whether every character exists in one of the three sets. A simple way is to verify that the set of characters in the word is a subset of a row set. If the condition holds for any row, add the word to the result list.
The key insight is that set lookups run in constant time, so each character check is efficient. The total work is proportional to the number of characters processed across all words. This solution directly models the keyboard layout and keeps the code readable. Time complexity is O(N) where N is the total number of characters across all words, and space complexity is O(1) since the keyboard rows contain a fixed number of letters. This approach heavily relies on fast membership checks using a Hash Table-style structure.
Approach 2: Mapping Characters to Rows (O(N) time, O(1) space)
Instead of storing three sets, build a mapping from each character to its keyboard row index (for example, {'q':1, 'w':1, ..., 'a':2, ..., 'z':3}). For each word, look up the row of the first character. Then iterate through the remaining characters and verify that every character maps to the same row number. If any character belongs to a different row, discard the word.
This approach uses a single hash map for constant-time row lookup. The benefit is that each character comparison becomes a quick integer equality check after the map lookup. It avoids repeated subset checks and is easy to implement in languages like Java or JavaScript. Time complexity remains O(N) because every character is visited once, and space complexity is O(1) since the map stores only 26 lowercase letters.
The input itself is a simple Array of words, and each word is processed character by character as a String. Both approaches scale linearly with the total input size and are efficient for typical interview constraints.
Recommended for interviews: The character-to-row mapping approach is typically what interviewers expect. It shows that you can preprocess a small lookup table and perform a single pass over the input. The set-based solution is equally correct and often shorter to implement, which makes it great for quick coding rounds. Showing both demonstrates that you understand the tradeoff between direct modeling (sets) and optimized lookups (mapping).
This approach involves creating a set for each row of the keyboard. Each word is then checked against these sets to see if all of its letters are contained entirely within one of the sets, making use of set comparison for simplicity.
We use sets to represent each keyboard row and for each word, transform it into a lowercase set. By checking if the set of the word is a subset of any of the row sets, we determine if the word can be typed on one keyboard row. The subset check leverages fast set operations in Python.
Time Complexity: O(n * m), where n is the number of words, and m is the maximum length of a word. Space Complexity: O(1) additional space, not counting the space taken by the output.
This approach maps each character to a corresponding row number. For each word, we check the row number of every character and ensure they all match. If they do, the word can be added to the list of results.
A map is used to first assign each character a row number. Then, for each word, we assign a row based on the first character and check each subsequent character to ensure they belong to the same row. This uses an `outer` label to break from nested loops efficiently.
Java
JavaScript
Time Complexity: O(n * m), where n is the number of words, and m is the maximum length of a word. Space Complexity: O(1) additional space for the map used to store row indices.
| Approach | Complexity |
|---|---|
| Using Sets for Each Keyboard Row | Time Complexity: O(n * m), where n is the number of words, and m is the maximum length of a word. Space Complexity: O(1) additional space, not counting the space taken by the output. |
| Mapping Characters to Rows | Time Complexity: O(n * m), where n is the number of words, and m is the maximum length of a word. Space Complexity: O(1) additional space for the map used to store row indices. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Using Sets for Each Keyboard Row | O(N) | O(1) | When you want a simple and readable implementation using set membership checks |
| Mapping Characters to Rows | O(N) | O(1) | Preferred in interviews for efficient lookups and a single pass per word |
500. Keyboard Row | LEETCODE EASY | BRUTE FORCE | CODE EXPLAINER • code Explainer • 4,006 views views
Watch 9 more video solutions →Practice Keyboard Row with our built-in code editor and test cases.
Practice on FleetCode