# LeetCode 925: Long Pressed Name

## Problem Restatement

We are given two strings:

| Item | Meaning |
|---|---|
| `name` | The name the friend intended to type |
| `typed` | The actual string produced by the keyboard |

Sometimes a key may be long pressed. If the intended character is `"a"`, the typed output may contain `"a"`, `"aa"`, `"aaa"`, and so on.

We need to return `true` if `typed` could be produced from `name` by long pressing some characters. Otherwise, return `false`.

For example:

```python
name = "alex"
typed = "aaleex"
```

This is valid because `"a"` and `"e"` were repeated.

But:

```python
name = "saeed"
typed = "ssaaedd"
```

This is invalid because the typed string does not contain enough consecutive `"e"` characters to match `"saeed"`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Two strings `name` and `typed` |
| Output | `True` if `typed` can be a long-pressed version of `name`, otherwise `False` |
| Constraint | Characters must appear in the same order |
| Important rule | Extra characters in `typed` are allowed only if they repeat the previous typed character |

## Examples

### Example 1

```python
name = "alex"
typed = "aaleex"
```

Output:

```python
True
```

Explanation:

`"a"` was typed as `"aa"`.

`"l"` was typed as `"l"`.

`"e"` was typed as `"ee"`.

`"x"` was typed as `"x"`.

So `typed` can come from `name`.

### Example 2

```python
name = "saeed"
typed = "ssaaedd"
```

Output:

```python
False
```

Explanation:

The intended name has two consecutive `"e"` characters.

But in `typed`, there is only one `"e"` before `"d"` starts.

A long press can add extra copies. It cannot remove required copies.

### Example 3

```python
name = "leelee"
typed = "lleeelee"
```

Output:

```python
True
```

The extra `"l"` and `"e"` characters can be explained as long presses.

### Example 4

```python
name = "laiden"
typed = "laiden"
```

Output:

```python
True
```

No long press is required. The original string itself is valid.

## First Thought: Compare Character Groups

A long press only creates extra copies of the same character next to itself.

So instead of thinking about single characters, we can think about consecutive groups.

For example:

```text
name  = "alex"
typed = "aaleex"
```

The groups are:

| String | Groups |
|---|---|
| `name` | `a`, `l`, `e`, `x` |
| `typed` | `aa`, `l`, `ee`, `x` |

Each group in `typed` must match the corresponding group in `name`.

Also, the typed group must be at least as long as the name group.

This works, but there is an even simpler scan.

## Key Insight

Use two pointers.

Let:

| Pointer | Meaning |
|---|---|
| `i` | Current position in `name` |
| `j` | Current position in `typed` |

We scan `typed` from left to right.

For each character `typed[j]`, there are two valid cases.

First, it may match the next needed character in `name`.

```python
name[i] == typed[j]
```

In that case, we consume one character from `name` by moving `i`.

Second, it may be an extra long-pressed character.

That is only valid when it equals the previous typed character:

```python
typed[j] == typed[j - 1]
```

If neither case is true, then `typed` contains a character that cannot be explained.

## Algorithm

Initialize `i = 0`.

Then scan each character `t` in `typed`.

For every position `j`:

1. If `i` is still inside `name` and `name[i] == typed[j]`, move `i` forward.
2. Otherwise, if `typed[j]` equals `typed[j - 1]`, treat it as a long press.
3. Otherwise, return `False`.

At the end, return whether all characters in `name` were consumed:

```python
i == len(name)
```

This final check matters.

For example:

```python
name = "alex"
typed = "ale"
```

The typed string follows the right order, but it never types `"x"`, so the answer is `False`.

## Correctness

The algorithm scans `typed` from left to right and keeps `i` as the number of characters already matched from `name`.

When `typed[j]` equals `name[i]`, the current typed character correctly represents the next required character of `name`, so advancing `i` is valid.

When `typed[j]` does not equal `name[i]`, it can only be valid if it is an extra copy caused by a long press. A long press repeats the same key as the previous typed character, so the condition `typed[j] == typed[j - 1]` exactly captures this case.

If neither condition holds, the current character in `typed` is neither the next required character nor a valid repeated character. Therefore, no long-press interpretation can produce `typed`, and returning `False` is correct.

After scanning all of `typed`, the algorithm returns `True` only if every character in `name` has been matched. If some character in `name` remains unmatched, then `typed` is missing required input, so it cannot be valid.

Therefore, the algorithm returns `True` exactly when `typed` can be produced from `name` by long pressing characters.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan `typed` once |
| Space | `O(1)` | We only store pointer `i` |

Here, `n = len(typed)`.

## Implementation

```python
class Solution:
    def isLongPressedName(self, name: str, typed: str) -> bool:
        i = 0

        for j, char in enumerate(typed):
            if i < len(name) and name[i] == char:
                i += 1
            elif j == 0 or char != typed[j - 1]:
                return False

        return i == len(name)
```

## Code Explanation

We start with:

```python
i = 0
```

This points to the next character in `name` that we still need to match.

Then we scan `typed`:

```python
for j, char in enumerate(typed):
```

If the current typed character matches the next required character in `name`, we consume that character:

```python
if i < len(name) and name[i] == char:
    i += 1
```

If it does not match, it must be a long-pressed duplicate of the previous typed character.

This condition rejects invalid characters:

```python
elif j == 0 or char != typed[j - 1]:
    return False
```

The `j == 0` check matters because the first character cannot be a long-pressed duplicate of a previous character.

Finally:

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

This confirms that every character in `name` was matched.

## Testing

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

    assert s.isLongPressedName("alex", "aaleex") is True
    assert s.isLongPressedName("saeed", "ssaaedd") is False
    assert s.isLongPressedName("leelee", "lleeelee") is True
    assert s.isLongPressedName("laiden", "laiden") is True
    assert s.isLongPressedName("pyplrz", "ppyypllr") is False
    assert s.isLongPressedName("vtkgn", "vttkgnn") is True
    assert s.isLongPressedName("alex", "ale") is False

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `"alex"`, `"aaleex"` | Basic valid long press |
| `"saeed"`, `"ssaaedd"` | Missing required repeated character |
| `"leelee"`, `"lleeelee"` | Multiple long-pressed groups |
| `"laiden"`, `"laiden"` | No long press |
| `"pyplrz"`, `"ppyypllr"` | Ends before matching all of `name` |
| `"vtkgn"`, `"vttkgnn"` | Valid repeated middle and final characters |
| `"alex"`, `"ale"` | Missing final character |