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.The key idea in #925 Long Pressed Name is to verify whether the typed string could result from long pressing characters while typing the original name. A common and efficient strategy is the two-pointer approach. Use one pointer for name and another for typed, comparing characters sequentially.
If both characters match, move both pointers forward. If they differ, check whether the current character in typed matches the previous character (indicating a long press). If so, only move the typed pointer forward. Otherwise, the typed string cannot represent a valid long press. Continue until the entire typed string is processed while ensuring all characters of name are matched in order.
This method efficiently validates the typing behavior without extra data structures. The algorithm runs in O(n) time where n is the length of typed, and uses O(1) extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Two Pointers (Name vs Typed Comparison) | O(n) | O(1) |
Pepcoding
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem or similar variations are sometimes asked in coding interviews because they test string traversal, pointer techniques, and careful handling of edge cases in linear scans.
Important edge cases include repeated characters in the typed string, missing characters from the original name, and extra characters that do not match the previous character. These must be carefully handled during pointer comparisons.
The optimal approach uses the two-pointer technique to compare the original name and the typed string. It checks whether extra repeated characters in the typed string correspond to long presses of the same character.
No special data structure is required for this problem. A simple two-pointer traversal over the two strings is sufficient to track matching characters and detect valid long presses.