Keyboard Row

Easy

Uber

3 views

Topics:

ArraysStrings

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).

Keyboard Row

Easy

Uber

3 views

Topics:

ArraysStrings

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).

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Are the input words case-sensitive, or should I treat them as case-insensitive?
Can the input array of words be empty or contain null/empty strings?
If a word can be typed using multiple rows, should I include it in the output?
What is the maximum length of a single word in the input array?
If no words can be typed using only one row, what should I return (e.g., an empty array, null)?

Brute Force Solution

Approach

The brute force approach to this problem is to check each word one by one against each of the keyboard rows. We determine which words can be typed using only one keyboard row by comparing the letters within the word against the letters in each row.

Here's how the algorithm would work step-by-step:

Take the first word from the list of words.
Check if all the letters of the first word can be typed using only the top row of the keyboard.
If they can, save this word.
If not, check if all the letters of the first word can be typed using only the middle row of the keyboard.
If they can, save this word.
If not, check if all the letters of the first word can be typed using only the bottom row of the keyboard.
If they can, save this word.
Move to the next word and repeat the same process of checking against each keyboard row.
Keep a list of all the words that can be typed using only one row of the keyboard.
Finally, return the list of these words.

Code Implementation

def find_words_from_keyboard_row(words):
    top_row = set('qwertyuiop')
    middle_row = set('asdfghjkl')
    bottom_row = set('zxcvbnm')

    result_words = []

    for word in words:
        word_lower = word.lower()

        # Check if the word can be typed using the top row
        if all(letter in top_row for letter in word_lower):
            result_words.append(word)

        # Check if the word can be typed using the middle row
        elif all(letter in middle_row for letter in word_lower):
            result_words.append(word)

        # Check if the word can be typed using the bottom row
        elif all(letter in bottom_row for letter in word_lower):
            result_words.append(word)

    return result_words

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(m*n) – Let m be the number of words in the input list and n be the average length of a word. For each word in the list (m), we iterate through its characters (average n) to check if they all belong to a single keyboard row. The check involves comparing each character against each row which has constant time, though the total number of characters to check per word depends on n. The dominant cost is the nested iteration: looping through each word, and looping through each character of that word. Thus the time complexity is O(m*n).

Space Complexity

O(N) – The primary auxiliary space usage comes from storing the list of words that can be typed using only one row of the keyboard. In the worst-case scenario, all N words in the input list satisfy this condition, thus requiring us to store all of them. Therefore, the auxiliary space complexity is directly proportional to the number of words in the input list. This results in an auxiliary space complexity of O(N), where N is the number of words in the input.

Optimal Solution

Approach

The key idea is to figure out which keyboard row each letter belongs to and then check if all letters of a word are on the same row. We can do this efficiently by using a simple way to quickly look up the row for each letter, rather than searching through rows repeatedly.

Here's how the algorithm would work step-by-step:

First, assign each of the three keyboard rows a unique identifier (like a number).
Then, for each letter in the alphabet, remember which row it belongs to. This gives us a quick way to find out the row for any letter.
Now, for each word, start by finding the row of its first letter.
Next, check if every other letter in the word is also on the same row as the first letter. If even one letter is on a different row, the word is not valid.
If all the letters in the word are on the same row, then we know this word can be typed using only one keyboard row, and we can keep it.
Repeat this process for every word in the given list to identify all the valid words.

Code Implementation

def find_words_from_keyboard_row(words):
    first_row = set('qwertyuiopQWERTYUIOP')
    second_row = set('asdfghjklASDFGHJKL')
    third_row = set('zxcvbnmZXCVBNM')
    row_map = {}

    for letter in first_row:
        row_map[letter] = 1
    for letter in second_row:
        row_map[letter] = 2
    for letter in third_row:
        row_map[letter] = 3

    result = []

    for word in words:
        #Determine which row the first letter exists on
        if not word:
            continue
        first_letter = word[0]
        row_number = row_map[first_letter]

        is_valid = True

        #Verify that all letters are in the same row
        for letter in word:
            if row_map[letter] != row_number:
                is_valid = False
                break

        if is_valid:
            result.append(word)

    return result

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(N * M) – Let N be the number of words in the input list and M be the maximum length of a word. The algorithm iterates through each of the N words. For each word, it iterates up to M times to check if all characters are on the same row. Looking up the keyboard row for a character takes constant time. Therefore, the overall time complexity is O(N * M), representing the nested iteration over words and characters within those words. In the worst case, every word needs M checks to confirm that it is typeable from one keyboard row.

Space Complexity

O(1) – The primary auxiliary space usage stems from storing the keyboard row mapping for each letter of the alphabet. Since the alphabet size is constant (26 letters), this mapping occupies a fixed amount of space. Furthermore, the algorithm uses a few variables to store the row of the first letter and potentially iterate through the word, which is also constant space. Therefore, the space complexity is independent of the number of words in the input list, N, and remains constant.

Edge Cases

Case	How to Handle
Empty input array of words	Return an empty list since there are no words to check.
Input array containing an empty string	Treat empty strings as not typeable on a single row and exclude them from the output.
Words with mixed-case letters	Convert each word to lowercase before checking to ensure case-insensitivity.
Words containing non-alphabetic characters (numbers, symbols, spaces)	Filter out such words or throw an error, as the problem description only mentions alphabetic characters.
Words with a length of 1	Words with only one character are always typeable on one row, so include them if applicable.
Words where the first character determines the row, but subsequent characters are from a different row	The solution should correctly identify that the word cannot be typed on a single row.
All words in the input can be typed on one row	The solution should return the original array as is since all words satisfy the condition.
No words in the input can be typed on one row	The solution should return an empty list since no words satisfy the condition.