Long Pressed Name — Solution in Python, Java & C++
Long Pressed Name solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Long Pressed Name is an easy coding problem on strings and two pointers, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Strings, Two Pointers
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Your friend is typing name on a keyboard, but sometimes a key gets held down too long and its character is repeated one or more extra times.
Given name and the string typed that actually came out, return true if typed could have been produced this way.
Example 1
Input: name = "alex", typed = "aaleex"
Output: true
Explanation: The a and the e were long-pressed.
Example 2
Input: name = "saeed", typed = "ssaaedd"
Output: false
Explanation: The e was typed only once but appears twice in the name.
Example 3
Input: name = "leelee", typed = "lleeelee"
Output: true
Constraints
1 <= name.length, typed.length <= 1000Both strings consist of lowercase English letters only.
Hints for Long Pressed Name
Hint 1
Walk both strings with two pointers, matching characters as they line up.
Hint 2
When they differ, the only legal explanation is that the current
typedcharacter repeats the previous one.Hint 3
At the end, every character of
namemust have been consumed.
How to solve Long Pressed Name
Long-pressing only ever inserts copies of a character that was already typed, so a greedy left-to-right match works: consume name when characters agree, and otherwise allow a repeat of the previous typed character.
Approach
- Set
iintonameandjintotyped, both at 0. - If
name[i] == typed[j], advance both. - Otherwise, if
typed[j]equalstyped[j-1], it is a long-press artefact — advancejonly. - Otherwise return
false. - After the loop return
i == name.lengthto confirm every character ofnamewas matched.
Why it works
Matching greedily is safe because a character of typed that equals name[i] is always better used as the match than as a repeat — using it as a repeat would leave name[i] needing a later, identical character, which the repeat rule would also have accepted.
Complexity
- Time —
O(n + m) - Space —
O(1)
Pitfalls
- Forgetting the final
i == name.lengthcheck acceptsname = "alex", typed = "aaleexa"… and worse, accepts atypedthat ran out early. - Comparing against
typed[j-1]requiresj > 0. - Counting character frequencies is not enough — order matters, and the run lengths must be at least as long in
typed.
Reference solution
Python
def isLongPressedName(name: str, typed: str) -> bool:
i = 0
j = 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)Java
public static boolean isLongPressedName(String name, String typed) {
int i = 0, j = 0;
while (j < typed.length()) {
if (i < name.length() && name.charAt(i) == typed.charAt(j)) { i++; j++; }
else if (j > 0 && typed.charAt(j) == typed.charAt(j - 1)) j++;
else return false;
}
return i == name.length();
}C++
bool isLongPressedName(string name, string typed) {
int i = 0, j = 0;
while (j < (int) typed.size()) {
if (i < (int) name.size() && name[i] == typed[j]) { i++; j++; }
else if (j > 0 && typed[j] == typed[j - 1]) j++;
else return false;
}
return i == (int) name.size();
}JavaScript
var isLongPressedName = function(name, typed) {
let i = 0, j = 0;
while (j < typed.length) {
if (i < name.length && name.charAt(i) === typed.charAt(j)) { i++; j++; }
else if (j > 0 && typed.charAt(j) === typed.charAt(j - 1)) j++;
else return false;
}
return i === name.length;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Two Pointers Technique