# LeetCode 500: Keyboard Row

## Problem Restatement

We are given an array of strings `words`.

Return the words that can be typed using letters from only one row of an American keyboard.

The keyboard rows are:

| Row | Letters |
|---|---|
| First row | `qwertyuiop` |
| Second row | `asdfghjkl` |
| Third row | `zxcvbnm` |

Letter case does not matter. For example, `A` and `a` belong to the same row. The word must use letters from only one row. The original word should be returned with its original casing.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Array of strings `words` |
| Output | Words that can be typed using one keyboard row |
| Case rule | Case-insensitive check |
| Return rule | Keep original word casing |

Function shape:

```python
def findWords(words: list[str]) -> list[str]:
    ...
```

## Examples

Example 1:

```python
words = ["Hello", "Alaska", "Dad", "Peace"]
```

Check each word:

| Word | Rows used | Valid |
|---|---|---|
| `"Hello"` | multiple rows | no |
| `"Alaska"` | second row only | yes |
| `"Dad"` | second row only | yes |
| `"Peace"` | multiple rows | no |

Answer:

```python
["Alaska", "Dad"]
```

Example 2:

```python
words = ["omk"]
```

The letters are not all from one row.

Answer:

```python
[]
```

Example 3:

```python
words = ["adsdf", "sfd"]
```

Both words use only the second row.

Answer:

```python
["adsdf", "sfd"]
```

## First Thought: Check Each Row

For each word, we can check whether all its letters are in one of the three keyboard rows.

Represent each row as a set:

```python
set("qwertyuiop")
set("asdfghjkl")
set("zxcvbnm")
```

Then convert the word to lowercase and check membership.

## Key Insight

A word is valid if the set of its lowercase letters is a subset of one keyboard row.

For example:

```python
word = "Alaska"
letters = set(word.lower())
```

The set is:

```python
{"a", "l", "s", "k"}
```

All of these letters are in:

```python
set("asdfghjkl")
```

So `"Alaska"` is valid.

For `"Hello"`:

```python
{"h", "e", "l", "o"}
```

These letters are split across rows, so it is invalid.

## Algorithm

Create three sets, one for each keyboard row.

For each word:

1. Convert it to lowercase.
2. Convert its letters to a set.
3. Check whether this set is a subset of any keyboard row.
4. If yes, append the original word to the answer.

Return the answer.

## Correctness

The algorithm checks each word after converting it to lowercase, so uppercase and lowercase letters are treated the same.

For a word to be typed using one row, every distinct letter in that word must belong to the same row. Converting the word to a set of letters captures exactly the distinct letters used by the word.

If this letter set is a subset of one keyboard row set, then every letter in the word can be typed from that row, so the word is valid.

If the letter set is not a subset of any row, then the word uses letters from at least two rows, so it cannot be typed using one row.

Therefore, the algorithm returns exactly the valid words.

## Complexity

Let:

| Symbol | Meaning |
|---|---|
| `n` | number of words |
| `L` | total number of characters across all words |

| Metric | Value | Why |
|---|---|---|
| Time | `O(L)` | Each character is processed a constant number of times |
| Space | `O(1)` excluding output | Keyboard row sets have fixed size |

## Implementation

```python
class Solution:
    def findWords(self, words: list[str]) -> list[str]:
        rows = [
            set("qwertyuiop"),
            set("asdfghjkl"),
            set("zxcvbnm"),
        ]

        ans = []

        for word in words:
            letters = set(word.lower())

            if any(letters <= row for row in rows):
                ans.append(word)

        return ans
```

## Code Explanation

The keyboard rows are stored as sets:

```python
rows = [
    set("qwertyuiop"),
    set("asdfghjkl"),
    set("zxcvbnm"),
]
```

For each word, convert it to lowercase and collect its letters:

```python
letters = set(word.lower())
```

This checks whether all letters come from one row:

```python
if any(letters <= row for row in rows):
```

The operator `<=` means “is subset of” for sets.

If the word is valid, append the original word:

```python
ans.append(word)
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.findWords(["Hello", "Alaska", "Dad", "Peace"]) == ["Alaska", "Dad"]
    assert s.findWords(["omk"]) == []
    assert s.findWords(["adsdf", "sfd"]) == ["adsdf", "sfd"]
    assert s.findWords(["TYPE", "row"]) == ["TYPE", "row"]
    assert s.findWords(["a", "S", "z"]) == ["a", "S", "z"]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `["Hello", "Alaska", "Dad", "Peace"]` | Main example |
| `["omk"]` | Invalid mixed-row word |
| `["adsdf", "sfd"]` | All valid second-row words |
| `["TYPE", "row"]` | Case-insensitive checking |
| Single-letter words | Any single letter is valid |