Long Pressed Name - Solution & Explanation

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.