Problem Description

The "Keyboard Row" problem asks you to filter a list of words and return only those that can be typed using letters from a single row of an American QWERTY keyboard. The keyboard rows are as follows:

• First row: q w e r t y u i o p
• Second row: a s d f g h j k l
• Third row: z x c v b n m

Given an array of strings words, you must return a new array containing only those words that can be typed by using letters from one row on the keyboard. Each word in the output should satisfy this requirement individually. The comparison should be case-insensitive, and you do not need to consider empty words.

Constraints:

• Each word contains only English letters (upper or lower case).
• Each word may use any number of letters, but all must be from a single row.
• Return the result in any order.

Thought Process

The first instinct might be to check, for each word, whether all its letters are present in any one of the keyboard rows. This could be done by iterating over each row and checking if the set of letters in the word is a subset of the set of letters in the row.

However, to optimize, we can avoid checking all rows for every word. Instead, we can map every letter to its corresponding row number. This way, for each word, we can quickly check if all its letters map to the same row. This approach reduces unnecessary checks and makes the solution more efficient.

The main challenge is ensuring case-insensitive comparison and efficiently associating each letter with its row.

Solution Approach

Let's break down the steps for an efficient solution:

1. Map each letter to a row:
   • Create a dictionary or array to associate each letter (regardless of case) with its keyboard row (1, 2, or 3).
2. Check each word:
   • For each word, convert it to lower case to ensure case-insensitive comparison.
   • Determine the row of the first letter.
   • Check if all other letters in the word belong to the same row by comparing their mapped values.
3. Collect valid words:
   • If a word passes the check, add it to the result list.

This method is efficient because it uses direct lookups to associate each letter with its row, and checks each word only once.

Example Walkthrough

Let's consider the input ["Hello", "Alaska", "Dad", "Peace"].

1. "Hello":
   • Letters: h, e, l, l, o
   • h: row 2, e: row 1, l: row 2, o: row 1
   • Not all letters are from the same row → Not included
2. "Alaska":
   • Letters: a, l, a, s, k, a
   • All letters in row 2 → Included
3. "Dad":
   • Letters: d, a, d
   • All letters in row 2 → Included
4. "Peace":
   • Letters: p, e, a, c, e
   • p: row 1, e: row 1, a: row 2, c: row 3
   • Letters from multiple rows → Not included

Output: ["Alaska", "Dad"]

Time and Space Complexity

Brute-force approach:

• For each word, check against each row by iterating through all letters in the row (up to 10 letters per row).
• If there are n words with average length k, the time complexity is O(n * k * r), where r is the number of rows (3).

• Mapping each letter to its row is O(1) per letter, as lookups in a dictionary or array are constant time.
• For each word, we check each letter once: O(n * k).
• Space complexity is O(1) for the mapping (since the alphabet size is constant) and O(n * k) for the output.

Thus, the optimized solution is linear in the total number of letters across all words.

Summary

The "Keyboard Row" problem is efficiently solved by mapping each letter to its keyboard row and checking if all letters in a word belong to the same row. This approach leverages constant-time lookups for each letter, resulting in a linear-time solution. The key insight is to avoid redundant row checks by precomputing letter-to-row mappings, making the algorithm both simple and efficient.

Code Implementation

class Solution:
    def findWords(self, words):
        row1 = set('qwertyuiop')
        row2 = set('asdfghjkl')
        row3 = set('zxcvbnm')
        result = []
        for word in words:
            lower = set(word.lower())
            if lower <= row1 or lower <= row2 or lower <= row3:
                result.append(word)
        return result
      

class Solution {
public:
    vector<string> findWords(vector<string>& words) {
        vector<string> res;
        string rows[] = {"qwertyuiop", "asdfghjkl", "zxcvbnm"};
        unordered_map<char, int> m;
        for (int i = 0; i < 3; ++i)
            for (char c : rows[i])
                m[c] = i, m[toupper(c)] = i;
        for (string word : words) {
            int row = m[word[0]];
            bool valid = true;
            for (char c : word)
                if (m[c] != row) {
                    valid = false;
                    break;
                }
            if (valid) res.push_back(word);
        }
        return res;
    }
};
      

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) {
            String lower = word.toLowerCase();
            if (allInRow(lower, row1) || allInRow(lower, row2) || allInRow(lower, row3)) {
                result.add(word);
            }
        }
        return result.toArray(new String[0]);
    }
    private boolean allInRow(String word, String row) {
        for (char c : word.toCharArray()) {
            if (row.indexOf(c) == -1) return false;
        }
        return true;
    }
}
      

var findWords = function(words) {
    const rows = [
        new Set('qwertyuiop'),
        new Set('asdfghjkl'),
        new Set('zxcvbnm')
    ];
    let result = [];
    for (let word of words) {
        let lower = word.toLowerCase();
        for (let row of rows) {
            if ([...lower].every(ch => row.has(ch))) {
                result.push(word);
                break;
            }
        }
    }
    return result;
};