Scale Engineer

Keyboard Row

Easy
#0487Time: O(N * L * R), where N is the number of words, L is the maximum length of a word, and R is the length of a keyboard row string. For each character in each word, we might call `row.indexOf()`, which takes O(R) time in the worst case.Space: O(K), where K is the number of valid words. The space is dominated by the list used to store the results. The space for the row strings is constant.1 company
Data structures
ArrayHash TableString
Companies
MathWorks

Prompt

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:

  • the first row consists of the characters "qwertyuiop",
  • the second row consists of the characters "asdfghjkl", and
  • the third row consists of the characters "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 <= 20
  • 1 <= words[i].length <= 100
  • words[i] consists of English letters (both lowercase and uppercase). 

Approaches

3 approaches with complexity analysis and trade-offs.

This approach uses a straightforward, brute-force method. We define three strings, one for each row of the keyboard. For each word in the input array, we check if all its characters belong to the first row. If not, we check if they all belong to the second row, and finally, the third row. This check is done by iterating through the word's characters and using string searching methods like indexOf to see if a character is present in the row string.

Algorithm

  1. Initialize an empty list result to store the valid words.
  2. Define three strings: row1 = "qwertyuiop", row2 = "asdfghjkl", and row3 = "zxcvbnm".
  3. For each word in the input words array, check if it can be typed using only characters from row1, row2, or row3.
  4. To do this, create a helper function isTypable(word, row) that iterates through each character of the word (converted to lowercase) and checks if the character exists in the given row string using row.indexOf(char).
  5. If isTypable returns true for any of the three rows, add the original word to the result list.
  6. After iterating through all words, convert the result list to a string array and return it.

Walkthrough

The core idea is to test each word against each of the three keyboard rows. We can write a helper function that takes a word and a row string. This function will iterate through every character of the word (after converting it to lowercase for case-insensitivity) and check if that character is present in the row string. If it finds any character that is not in the row, it immediately returns false. If all characters are found in the row, it returns true. The main function then calls this helper for each word with each of the three rows. If any of the calls return true, the word is added to our result list.

import java.util.ArrayList;import java.util.List; class Solution {    public String[] findWords(String[] words) {        String row1 = "qwertyuiop";        String row2 = "asdfghjkl";        String row3 = "zxcvbnm";        List<String> result = new ArrayList<>();         for (String word : words) {            if (isTypable(word.toLowerCase(), row1) ||                isTypable(word.toLowerCase(), row2) ||                isTypable(word.toLowerCase(), row3)) {                result.add(word);            }        }        return result.toArray(new String[0]);    }     private boolean isTypable(String word, String row) {        for (char c : word.toCharArray()) {            if (row.indexOf(c) == -1) {                return false;            }        }        return true;    }}

Complexity

Time

O(N * L * R), where N is the number of words, L is the maximum length of a word, and R is the length of a keyboard row string. For each character in each word, we might call `row.indexOf()`, which takes O(R) time in the worst case.

Space

O(K), where K is the number of valid words. The space is dominated by the list used to store the results. The space for the row strings is constant.

Trade-offs

Pros

  • Simple to understand and implement with minimal setup.

  • Requires very little extra space, aside from the result list.

Cons

  • This approach is inefficient because it involves repeated linear scans of the row strings. The indexOf or contains method on a string has a time complexity proportional to the length of the string, leading to a higher overall time complexity.

Solutions

public class Solution {    public string[] FindWords(string[] words) {        string s = "12210111011122000010020202";        IList < string > ans = new List < string > ();        foreach(string w in words) {            char x = s[char.ToLower(w[0]) - 'a'];            bool ok = true;            for (int i = 1; i < w.Length; ++i) {                if (s[char.ToLower(w[i]) - 'a'] != x) {                    ok = false;                    break;                }            }            if (ok) {                ans.Add(w);            }        }        return ans.ToArray();    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem