Watch 10 video solutions for Long Pressed Name, a easy level problem involving Two Pointers, String. This walkthrough by Pepcoding has 63,658 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Your friend is typing his name into a keyboard. Sometimes, when typing a character c, the key might get long pressed, and the character will be typed 1 or more times.
You examine the typed characters of the keyboard. Return True if it is possible that it was your friends name, with some characters (possibly none) being long pressed.
Example 1:
Input: name = "alex", typed = "aaleex" Output: true Explanation: 'a' and 'e' in 'alex' were long pressed.
Example 2:
Input: name = "saeed", typed = "ssaaedd" Output: false Explanation: 'e' must have been pressed twice, but it was not in the typed output.
Constraints:
1 <= name.length, typed.length <= 1000name and typed consist of only lowercase English letters.Problem Overview: You are given two strings: name and typed. The string typed represents what appears on the keyboard when someone types name, but some characters might be long‑pressed. A long press repeats the same character multiple times. The task is to verify whether typed could have been produced from name while preserving the character order.
Approach 1: Two Pointers Technique (O(n) time, O(1) space)
This is the optimal approach and the one interviewers expect. Use two pointers: one for name and one for typed. Iterate through typed while matching characters with name. When both pointers match, move both forward. If they don't match but the current typed character equals the previous character in typed, treat it as a long press and advance only the typed pointer. If neither condition holds, the string is invalid. This works because long presses only repeat the previous character without changing order. The scan runs once across the strings, giving O(n) time complexity with O(1) extra space.
This pattern is common in Two Pointers problems where two sequences must be compared while preserving order. Since you only track indices and a previous character check, the implementation stays simple and memory efficient.
Approach 2: Frequency Count Comparison (O(n) time, O(1) space)
Another way to reason about the problem is by grouping consecutive characters in both strings. For example, name = "alex" becomes groups like a(1), l(1), e(1), x(1). If typed = "aaleex", the groups are a(2), l(1), e(2), x(1). Iterate through both strings and count the length of each consecutive character block. For the strings to be valid, the characters must match and the count in typed must be greater than or equal to the count in name. If typed has fewer occurrences of a character than name, it means a required character was skipped.
This approach relies on basic String processing and run-length counting. Complexity remains O(n) because each character is processed once while forming groups. Space complexity stays O(1) since counts are tracked using simple variables.
Recommended for interviews: The Two Pointers solution is the expected answer. It demonstrates strong control over sequential comparison problems and minimal memory usage. The frequency group method is also valid but slightly more verbose. Showing the brute reasoning first (character repetition groups) and then optimizing to the pointer scan signals strong problem‑solving ability.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Pointers Technique | O(n) | O(1) | Best general solution for comparing sequential strings with possible repeats |
| Frequency Count (Character Groups) | O(n) | O(1) | Useful when reasoning about consecutive character blocks or explaining the long‑press rule clearly |