LeetCode 925: Long Pressed Name

Problem Restatement

We are given two strings:

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:

name = "alex"
typed = "aaleex"

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

But:

name = "saeed"
typed = "ssaaedd"

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

Input and Output

Examples

Example 1

name = "alex"
typed = "aaleex"

Output:

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

name = "saeed"
typed = "ssaaedd"

Output:

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

name = "leelee"
typed = "lleeelee"

Output:

True

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

Example 4

name = "laiden"
typed = "laiden"

Output:

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:

name  = "alex"
typed = "aaleex"

The groups are:

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:

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.

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:

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:

i == len(name)

This final check matters.

For example:

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

Here, n = len(typed).

Implementation

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:

i = 0

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

Then we scan typed:

for j, char in enumerate(typed):

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

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:

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:

return i == len(name)

This confirms that every character in name was matched.

Testing

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