925. Long Pressed Name
Model: qwen2.5-coder:14b
Topics: Two Pointers,String
FAANG asked: 1
Acceptance rate: 37.5%
Problem Breakdown
The problem asks us to determine if a given string typed could be a result of typing another string name where some characters might have been long-pressed. In other words, we need to check if typed is a possible “long-pressed” version of name.
Inputs:
name: A string representing the original name.typed: A string representing the typed output.
Outputs:
- A boolean value indicating whether
typedcould be a long-pressed version ofname.
Implicit Constraints/Edge Cases:
- If
typedis shorter thanname, it cannot be a valid long-pressed version. - If
typedcontains characters not present inname, it’s invalid. - Characters that appear multiple times in
typedmust have appeared at least as many times consecutively inname.
Intuition
A brute-force approach would involve generating all possible long-pressed versions of name and checking if any match typed. However, this is computationally expensive with a time complexity of O(2^n) due to the exponential growth of possibilities.
The key insight is that for each character in typed, it must either match the current character in name or be a long-pressed version of the previous character. This allows us to use a two-pointer technique to traverse both strings efficiently.
Approach
- Initialize two pointers,
iandj, to traversenameandtyped, respectively. - Iterate through both strings:
- If characters at
name[i]andtyped[j]match, move both pointers forward (i++,j++). - If they don’t match, check if the current character in
typedis the same as the previous character intyped. If so, move only thetypedpointer forward (j++). Otherwise, returnFalse.
- If characters at
- After the loop, ensure that all characters in
namehave been matched by checking ifihas reached the end ofname.
Complexity Analysis
- Time Complexity: O(n + m), where n is the length of
nameand m is the length oftyped. We traverse both strings once. - Space Complexity: O(1). We use only a constant amount of extra space for pointers.
Solution
def isLongPressedName(name: str, typed: str) -> bool:
i, j = 0, 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)
Edge Cases Handled
- If
typedis shorter thanname, the loop will not complete, andiwill not reach the end ofname, returningFalse. - If
typedcontains characters not present inname, the mismatch check (name[i] != typed[j]) will fail at some point. - If
typedhas extra characters that are not long-pressed versions of consecutive characters inname, the mismatch check will also fail.