How do you solve Long Pressed Name on LeetCode?

Long Pressed Name (LeetCode #925) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: The order of characters in 'name' must be preserved in 'typed'.

What is the time complexity of Long Pressed Name?

The optimal solution for Long Pressed Name runs in O(n) time and uses O(1) space. The optimal solution runs in O(n) time because we traverse each string only once, making it efficient for larger inputs.

What is the brute force solution for Long Pressed Name?

The brute force approach for Long Pressed Name is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks every possible way to match the typed string to the friend's name. It essentially tries to simulate the typing process, comparing each character in sequence. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Long Pressed Name?

Long Pressed Name uses the following concepts: Two Pointers, String. The recommended patterns to study are: Two Pointers, String Matching.

What are the interview tips for Long Pressed Name?

Always clarify the problem statement and constraints before jumping into coding. Think about edge cases, such as all characters being long pressed or no long presses at all. Practice explaining your thought process as you code, as this helps interviewers understand your approach.

What are common mistakes when solving Long Pressed Name?

Not checking if the previous character in 'typed' is the same when a mismatch occurs. Assuming that the length of 'typed' must always be greater than or equal to 'name'.

#925

Long Pressed Name

Easy

Two PointersStringTwo PointersString Matching

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal approach uses two pointers to traverse both strings simultaneously, ensuring that we only move forward in 'typed' when we see a match or a valid long press. This is efficient and straightforward.

⚙️

Algorithm

5 steps

1Step 1: Initialize two pointers, one for 'name' and one for 'typed'.
2Step 2: Traverse 'typed' while comparing it to 'name'.
3Step 3: If characters match, move both pointers forward.
4Step 4: If characters don't match, check if the current character in 'typed' is the same as the previous one (indicating a long press). If not, return False.
5Step 5: After the loop, ensure all characters in 'name' have been matched.

solution.py11 lines

1def isLongPressedName(name: str, typed: str) -> bool:
2    i, j = 0, 0
3    while j < len(typed):
4        if i < len(name) and name[i] == typed[j]:
5            i += 1
6        elif j > 0 and typed[j] == typed[j - 1]:
7            pass
8        else:
9            return False
10        j += 1
11    return i == len(name)

ℹ

Complexity note: The optimal solution runs in O(n) time because we traverse each string only once, making it efficient for larger inputs.

1The order of characters in 'name' must be preserved in 'typed'.
2Long presses can only extend the sequence of the same character.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.