LeetCode 925 - Long Pressed Name

In this problem, we are given two strings, name and typed. The string name represents the intended sequence of characters your friend wanted to type. The string typed represents the actual characters that appeared on the screen.

leetcodeeasytwo-pointersstring

LeetCode Problem 925

Difficulty: 🟢 Easy
Topics: Two Pointers, String

Solution

Problem Understanding

In this problem, we are given two strings, name and typed.

The string name represents the intended sequence of characters your friend wanted to type. The string typed represents the actual characters that appeared on the screen.

The complication is that some keys may have been long pressed. A long press means that when a character is typed once in name, it may appear multiple consecutive times in typed.

For example:

  • name = "alex"
  • typed = "aaleex"

This is valid because:

  • 'a' was long pressed and became "aa"
  • 'e' was long pressed and became "ee"

The relative order of characters must remain the same. Long pressing only allows repeating the current character, not inserting new unrelated characters or skipping required characters.

The goal is to determine whether typed could realistically have been produced from name using zero or more long presses.

The constraints are small:

  • 1 <= name.length, typed.length <= 1000
  • Both strings contain only lowercase English letters.

Since the strings are short, even less efficient approaches could work within limits. However, the problem is fundamentally about sequential matching, which naturally suggests a linear scan solution.

Several edge cases are important:

  • typed may contain extra repeated characters that are valid long presses.
  • typed may skip characters that appear in name.
  • typed may introduce completely different characters.
  • typed may end with repeated copies of the final character.
  • typed may be shorter than name, which is automatically invalid because every character in name must appear at least once.

For example:

  • name = "alex"
  • typed = "ale"

This is invalid because 'x' never appears.

Another example:

  • name = "saeed"
  • typed = "ssaaedd"

This is invalid because the second 'e' from name is missing.

Approaches

Brute Force Approach

A brute force strategy would attempt to simulate all possible long press combinations.

For each character in name, we could consider that it may appear one or more times in typed. We could recursively try every valid grouping and see whether some arrangement exactly reconstructs typed.

For example, if name = "alex" and typed = "aaleex", the brute force method might try:

  • 'a' -> "a" or "aa"
  • 'l' -> "l"
  • 'e' -> "e" or "ee"
  • 'x' -> "x"

Eventually, one valid decomposition would match the entire typed string.

This approach is correct because it explores every possible way long presses could occur. However, it is inefficient because the number of possibilities grows exponentially when many repeated characters exist.

Although the constraints are small enough that some inefficient solutions may pass, this approach is unnecessarily complex.

Optimal Two Pointer Approach

The key observation is that both strings must be processed in order.

Every character in typed must satisfy one of two conditions:

  1. It matches the current character in name, meaning we advance both pointers.
  2. It matches the previous character in typed, meaning it is a long press of the last valid character.

If neither condition holds, the strings are incompatible.

This naturally leads to a two pointer solution:

  • One pointer traverses name
  • One pointer traverses typed

We greedily match characters from left to right.

This works because long presses only duplicate existing characters. They never reorder characters or introduce new transitions.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) in the worst case O(n) recursion stack Tries all possible long press groupings
Optimal O(n + m) O(1) Linear two pointer scan

Algorithm Walkthrough

  1. Initialize two pointers:
  • i for name
  • j for typed

Both start at index 0. 2. Traverse the typed string while j < len(typed). 3. At each step, first check whether:

  • i < len(name)
  • name[i] == typed[j]

If true, this character matches normally. Move both pointers forward. 4. Otherwise, check whether the current character in typed equals the previous character in typed.

This means:

  • j > 0
  • typed[j] == typed[j - 1]

If true, the current character is simply a long press repetition. Move only j. 5. If neither condition is true, return False.

This means the current character in typed cannot be explained by either:

  • matching the next character in name
  • repeating the previous typed character
  1. After finishing the traversal of typed, verify that all characters in name were matched.

Return:

  • True if i == len(name)
  • False otherwise

Why it works

The algorithm maintains the invariant that all characters before i in name have been correctly matched against all processed characters before j in typed.

Whenever characters match directly, both pointers advance.

Whenever a repeated character appears in typed, it is only valid if it repeats the immediately previous valid character, which corresponds exactly to the definition of a long press.

If a character cannot satisfy either rule, there is no legal way to interpret it, so the answer must be False.

Because the algorithm processes characters sequentially and never skips unmatched required characters, it correctly validates whether typed can result from long pressing.

Python Solution

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

        while j < len(typed):
            if i < len(name) and name[i] == typed[j]:
                i += 1
                j += 1
            elif j > 0 and typed[j] == typed[j - 1]:
                j += 1
            else:
                return False

        return i == len(name)

The implementation follows the two pointer strategy directly.

The pointer i tracks progress through name, while j tracks progress through typed.

Inside the loop, the first condition checks whether the current characters match normally. If they do, both pointers advance because one intended character has been successfully matched.

The second condition handles long presses. If the current character in typed equals the previous typed character, then this extra occurrence can be explained as a repeated key press. In this case, only j advances.

If neither condition applies, the current character is invalid, so the function immediately returns False.

After processing all characters in typed, the final check ensures that every character in name was matched. If some characters remain unmatched, the typing sequence is incomplete.

Go Solution

func isLongPressedName(name string, typed string) bool {
	i := 0
	j := 0

	for j < len(typed) {
		if i < len(name) && name[i] == typed[j] {
			i++
			j++
		} else if j > 0 && typed[j] == typed[j-1] {
			j++
		} else {
			return false
		}
	}

	return i == len(name)
}

The Go implementation is nearly identical to the Python version.

Since Go strings are byte indexed and the problem guarantees lowercase English letters, direct indexing with name[i] and typed[j] is safe.

No additional memory allocations or helper data structures are required. The implementation uses constant extra space and performs a single linear scan.

Worked Examples

Example 1

Input:

name = "alex"
typed = "aaleex"
Step i j name[i] typed[j] Action
1 0 0 a a Match, move both
2 1 1 l a Long press of previous 'a', move j
3 1 2 l l Match, move both
4 2 3 e e Match, move both
5 3 4 x e Long press of previous 'e', move j
6 3 5 x x Match, move both

Final state:

  • i = 4
  • len(name) = 4

Return True.

Example 2

Input:

name = "saeed"
typed = "ssaaedd"
Step i j name[i] typed[j] Action
1 0 0 s s Match
2 1 1 a s Long press of previous 's'
3 1 2 a a Match
4 2 3 e a Long press of previous 'a'
5 2 4 e e Match
6 3 5 e d Invalid transition

At step 6:

  • Expected another 'e'
  • Got 'd'
  • 'd' is not a repeat of previous typed character 'e'

Return False.

Complexity Analysis

Measure Complexity Explanation
Time O(n + m) Each pointer moves forward at most once through its string
Space O(1) Only a few integer variables are used

The algorithm performs a single pass over the input strings. Each iteration advances at least one pointer, so the total number of operations is linear in the combined lengths of the strings.

No auxiliary data structures are allocated, which gives constant extra space usage.

Test Cases

solution = Solution()

assert solution.isLongPressedName("alex", "aaleex") == True
# Basic valid long presses

assert solution.isLongPressedName("saeed", "ssaaedd") == False
# Missing required repeated character

assert solution.isLongPressedName("leelee", "lleeelee") == True
# Multiple long presses throughout the string

assert solution.isLongPressedName("laiden", "laiden") == True
# Exact match without long presses

assert solution.isLongPressedName("vtkgn", "vttkgnn") == True
# Long presses in the middle and end

assert solution.isLongPressedName("alex", "alexxr") == False
# Extra unrelated trailing character

assert solution.isLongPressedName("pyplrz", "ppyypllr") == False
# Missing characters near the end

assert solution.isLongPressedName("a", "aaaa") == True
# Single character repeated many times

assert solution.isLongPressedName("abcd", "abc") == False
# Typed string shorter than name

assert solution.isLongPressedName("abc", "abccccc") == True
# Valid repeated final character

assert solution.isLongPressedName("abc", "aabbcc") == True
# Every character long pressed

assert solution.isLongPressedName("abc", "aabbdcc") == False
# Invalid character ordering

Test Summary

Test Why
"alex", "aaleex" Standard valid example
"saeed", "ssaaedd" Missing required repeated character
"leelee", "lleeelee" Multiple long press groups
"laiden", "laiden" No long presses
"vtkgn", "vttkgnn" Long presses at different positions
"alex", "alexxr" Invalid extra character
"pyplrz", "ppyypllr" Incomplete matching
"a", "aaaa" Single repeated character
"abcd", "abc" Typed string too short
"abc", "abccccc" Repeated final character
"abc", "aabbcc" All characters repeated
"abc", "aabbdcc" Incorrect ordering

Edge Cases

One important edge case occurs when typed contains extra repeated characters at the end. For example:

name = "abc"
typed = "abccccc"

A naive implementation might incorrectly reject this because typed is longer than name. However, repeated trailing characters are perfectly valid long presses. The algorithm handles this correctly because repeated characters are allowed as long as they match the previous typed character.

Another important edge case is when typed is shorter than name.

name = "abcd"
typed = "abc"

This situation is invalid because every character from name must appear at least once in typed. The algorithm naturally detects this because pointer i never reaches the end of name, causing the final condition i == len(name) to fail.

A third important edge case involves invalid character transitions.

name = "abc"
typed = "aabbdcc"

The character 'd' appears unexpectedly between valid groups. It is neither the next expected character from name nor a repetition of the previous typed character. The algorithm immediately returns False when this invalid transition is encountered.

Another subtle edge case is repeated characters already present in name.

name = "aabb"
typed = "aaaabbbb"

The algorithm still works correctly because matching always prioritizes advancing through name whenever possible. Only surplus repeated characters are treated as long presses.