# LeetCode 524: Longest Word in Dictionary through Deleting

## Problem Restatement

We are given:

```python
s
dictionary
```

We may delete some characters from `s`.

We need to return the longest string in `dictionary` that can be formed as a subsequence of `s`.

If multiple answers have the same length, return the lexicographically smallest one.

If no dictionary word can be formed, return the empty string.

The official problem asks us to find the longest dictionary word obtainable by deleting characters from `s`. If several answers have the same length, choose the lexicographically smallest one. ([leetcode.com](https://leetcode.com/problems/longest-word-in-dictionary-through-deleting/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | String `s`, list of strings `dictionary` |
| Output | Best matching dictionary word |
| Subsequence rule | Delete characters without changing order |
| Tie-breaking | Lexicographically smallest among longest words |

Function shape:

```python
class Solution:
    def findLongestWord(
        self,
        s: str,
        dictionary: List[str]
    ) -> str:
        ...
```

## Examples

Example 1:

```python
s = "abpcplea"
dictionary = ["ale", "apple", "monkey", "plea"]
```

Possible subsequences include:

| Word | Is subsequence? |
|---|---|
| `"ale"` | Yes |
| `"apple"` | Yes |
| `"monkey"` | No |
| `"plea"` | Yes |

The longest valid word is:

```text
apple
```

So the answer is:

```python
"apple"
```

Example 2:

```python
s = "abpcplea"
dictionary = ["a", "b", "c"]
```

All words have length `1`.

The lexicographically smallest is:

```text
a
```

So the answer is:

```python
"a"
```

## First Thought: Test Every Dictionary Word

For each dictionary word:

1. Check whether it is a subsequence of `s`
2. Keep the best valid candidate

This works because the dictionary size is manageable.

The main subproblem is efficient subsequence checking.

## Key Insight

Use two pointers.

To check whether word `w` is a subsequence of `s`:

1. Scan through `s`
2. Advance a pointer in `w` whenever characters match
3. If all characters of `w` are matched, then `w` is a subsequence

Example:

```python
s = "abpcplea"
w = "apple"
```

Matching process:

| `s` character | Needed character | Match? |
|---|---|---|
| `a` | `a` | Yes |
| `b` | `p` | No |
| `p` | `p` | Yes |
| `c` | `p` | No |
| `p` | `p` | Yes |
| `l` | `l` | Yes |
| `e` | `e` | Yes |

All characters were matched.

So `"apple"` is a subsequence.

## Choosing the Best Candidate

Suppose several words are valid subsequences.

We prefer:

1. Larger length
2. Lexicographically smaller if lengths are equal

So for candidate `word`, update the answer if:

```python
len(word) > len(answer)
```

or:

```python
len(word) == len(answer)
and word < answer
```

## Algorithm

Initialize:

```python
answer = ""
```

For each word in `dictionary`:

1. Check whether it is a subsequence of `s`
2. If valid:
   - update `answer` if the word is longer
   - or if same length but lexicographically smaller

Return `answer`.

## Correctness

The helper function correctly determines whether a dictionary word is a subsequence of `s` by scanning `s` left to right and matching characters in order.

A word is considered valid exactly when all of its characters can be matched in sequence inside `s`.

The algorithm checks every dictionary word, so every valid candidate is considered.

The update rule always keeps the best candidate according to the problem ordering:

1. Prefer larger length
2. For equal lengths, prefer lexicographically smaller words

Therefore, after processing the entire dictionary, `answer` is exactly the required output.

If no word is a subsequence of `s`, the answer remains the empty string, which is correct.

## Complexity

Let:

| Symbol | Meaning |
|---|---|
| `n` | Length of `s` |
| `d` | Number of dictionary words |
| `m` | Average dictionary word length |

| Metric | Value | Why |
|---|---|---|
| Time | `O(d * n)` worst case | Each subsequence check may scan `s` |
| Space | `O(1)` | Only pointers and counters |

More precisely, the total work is proportional to all subsequence checks.

## Implementation

```python
from typing import List

class Solution:
    def findLongestWord(
        self,
        s: str,
        dictionary: List[str]
    ) -> str:

        def is_subsequence(word: str) -> bool:
            i = 0

            for ch in s:
                if i < len(word) and word[i] == ch:
                    i += 1

            return i == len(word)

        answer = ""

        for word in dictionary:
            if is_subsequence(word):
                if (
                    len(word) > len(answer)
                    or (
                        len(word) == len(answer)
                        and word < answer
                    )
                ):
                    answer = word

        return answer
```

## Code Explanation

The helper function checks subsequences:

```python
def is_subsequence(word: str) -> bool:
```

`i` tracks how many characters of `word` have been matched:

```python
i = 0
```

Scan through `s`:

```python
for ch in s:
```

Advance the pointer when characters match:

```python
if i < len(word) and word[i] == ch:
    i += 1
```

If all characters were matched:

```python
return i == len(word)
```

then the word is a subsequence.

Now process every dictionary word:

```python
for word in dictionary:
```

If it is valid:

```python
if is_subsequence(word):
```

update the answer if:

```python
len(word) > len(answer)
```

or if lengths tie and the new word is lexicographically smaller:

```python
word < answer
```

## Testing

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

    assert (
        s.findLongestWord(
            "abpcplea",
            ["ale", "apple", "monkey", "plea"]
        )
        == "apple"
    )

    assert (
        s.findLongestWord(
            "abpcplea",
            ["a", "b", "c"]
        )
        == "a"
    )

    assert (
        s.findLongestWord(
            "bab",
            ["ba", "ab", "a", "b"]
        )
        == "ab"
    )

    assert (
        s.findLongestWord(
            "abc",
            ["d", "e"]
        )
        == ""
    )

    assert (
        s.findLongestWord(
            "aaa",
            ["aa", "aaa", "aaaa"]
        )
        == "aaa"
    )

    print("all tests passed")
```

Test meaning:

| Test | Why |
|---|---|
| Standard example | Longest valid subsequence |
| Same-length candidates | Lexicographic tie-breaking |
| `"ba"` vs `"ab"` | Lexicographic comparison |
| No valid dictionary word | Empty string case |
| Word longer than source | Must reject impossible subsequence |