#925

Easy

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Long Pressed Name

Check if a typed string could result from long pressing characters while typing a given name using a two-pointer scan.

Problem Statement

Your friend is typing their name on a keyboard, but sometimes a key may be long pressed, resulting in a character appearing one or more times consecutively. You receive the typed string and need to check if it could match the intended name with some characters possibly repeated due to long presses.

Return true if the typed string can correspond to the original name under this long-press behavior, and false otherwise. For example, if name = "alex" and typed = "aaleex", the output is true because 'a' and 'e' were long pressed, but if name = "saeed" and typed = "ssaaedd", the output is false because 'e' is missing one required press.

Examples

Example 1

Input: name = "alex", typed = "aaleex"

Output: true

'a' and 'e' in 'alex' were long pressed.

Example 2

Input: name = "saeed", typed = "ssaaedd"

Output: false

'e' must have been pressed twice, but it was not in the typed output.

Constraints

1 <= name.length, typed.length <= 1000
name and typed consist of only lowercase English letters.

Solution Approach

Two-pointer traversal

Initialize two pointers i and j at the start of name and typed. Move both pointers forward when characters match. If characters in typed repeat but match the previous character in name, advance j only. Any mismatch indicates a false result.

Invariant tracking

Maintain the invariant that every typed character either matches the current character in name or is a repeated long press of the previous character. Violating this invariant immediately signals the typed string cannot correspond to name.

Final check

After scanning, ensure the name pointer has reached the end. If it hasn't, some characters were not typed or were skipped, leading to a false result. Otherwise, return true as all characters align under long-press rules.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n + m) where n and m are the lengths of name and typed because each pointer scans its string once. Space complexity is O(1) as no extra data structures are used beyond pointer variables.

What Interviewers Usually Probe

Expect linear scanning solutions rather than nested loops.
Check edge cases like repeated characters at the start or end of typed.
Clarify whether empty strings or single-character names are possible inputs.

Common Pitfalls or Variants

Common pitfalls

Assuming all repeated characters are valid without matching the name sequence.
Failing to check the final position of the name pointer after traversal.
Ignoring consecutive repeated characters at the start or end of typed.

Follow-up variants

Allow uppercase letters and consider case-sensitive matching.
Count minimal number of long presses required to produce typed from name.
Check if typed can result from name with both long presses and skipped characters.

FAQ

What is the best approach for the Long Pressed Name problem?

Using two-pointer scanning with invariant tracking ensures each character in typed aligns with the name or a valid long press.

Can this problem be solved recursively?

While recursion is possible, it complicates handling consecutive repeated characters and increases space usage unnecessarily.

How do I handle characters repeated multiple times in typed?

Advance the typed pointer while the character matches the previous name character; only advance the name pointer when characters match exactly.

What if typed has extra characters not in name?

If a character in typed neither matches the current nor the previous character in name, return false immediately.

Does GhostInterview explain failure modes for this problem?

Yes, it highlights skipped name characters and invalid long presses that often cause incorrect outputs in interviews.

terminal

Solution

Solution 1: Two Pointers

We use two pointers $i$ and $j$ to point to the first character of the strings `typed` and `name` respectively, and then start traversing. If `typed[j]` is not equal to `name[i]`, it means the two strings do not match, and we directly return `False`. Otherwise, we find the next position of the continuous identical characters, denoted as $x$ and $y$ respectively. If $x - i > y - j$, it means the number of characters in `typed` is less than the number of characters in `name`, and we directly return `False`. Otherwise, we update $i$ and $j$ to $x$ and $y$ respectively, continue traversing, until $i$ and $j$ have traversed `name` and `typed` respectively, and return `True`.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def isLongPressedName(self, name: str, typed: str) -> bool:
        m, n = len(name), len(typed)
        i = j = 0
        while i < m and j < n:
            if name[i] != typed[j]:
                return False
            x = i + 1
            while x < m and name[x] == name[i]:
                x += 1
            y = j + 1
            while y < n and typed[y] == typed[j]:
                y += 1
            if x - i > y - j:
                return False
            i, j = x, y
        return i == m and j == n

Continue Practicing

#917 reverse only letters #942 di string match #844 backspace string compare