Long Pressed Name
Long Pressed Name is a easy arrays & hashing problem solved with the two pointer pattern.
The best approach, optimal (two pointers), runs in O(n + m) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (compare run-length groups) up.
Problem
A friend is typing their name on a keyboard whose keys sometimes stick: when a key sticks, the character it types appears one or more extra times in a row. No character is ever skipped or replaced.
Given the intended name and the actual typed string, return true if typed could have been produced by typing name with some keys held down too long, and false otherwise.
Examples
Example 1
- Input
name = "mira", typed = "miiiraa"- Output
true- Why
- The
ikey was held for three characters and theakey for two; nothing else changed.
Example 2
- Input
name = "otto", typed = "oto"- Output
false- Why
- A held key can only add characters. The double
tbecame a singlet, so a character is missing.
Example 3
- Input
name = "cab", typed = "ccabbd"- Output
false- Why
- Everything up to
ccabbis fine, but the trailingdnever appears in the name.
Constraints
1 <= name.length, typed.length <= 1000- Both strings contain only lowercase English letters.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 15 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (compare run-length groups) | O(n + m) | O(n + m) |
| Optimal (two pointers) | O(n + m) | O(1) |
1Brute force (compare run-length groups)
O(n + m)Each string is scanned once to build its runs and the runs are compared once.O(n + m)The run lists can hold one entry per character in the worst case.Encode both strings as lists of (letter, count) runs. typed is valid exactly when both lists have the same length, the letters agree run by run, and each run in typed is at least as long as the run in name.
- Build the runs of name and of typed.
- If the number of runs differs, return false.
- For each run index k: letters must match and typedCount[k] >= nameCount[k].
- Return true if every run passes.
class Solution {
public boolean isLongPressedName(String name, String typed) {
List<int[]> a = runs(name), b = runs(typed);
if (a.size() != b.size()) return false;
for (int k = 0; k < a.size(); k++) {
if (a.get(k)[0] != b.get(k)[0] || b.get(k)[1] < a.get(k)[1]) return false;
}
return true;
}
private List<int[]> runs(String s) {
List<int[]> out = new ArrayList<>();
int i = 0;
while (i < s.length()) {
int j = i;
while (j < s.length() && s.charAt(j) == s.charAt(i)) j++;
out.add(new int[] { s.charAt(i), j - i });
i = j;
}
return out;
}
}class Solution:
def isLongPressedName(self, name: str, typed: str) -> bool:
def runs(s: str) -> List[List]:
out = []
i = 0
while i < len(s):
j = i
while j < len(s) and s[j] == s[i]:
j += 1
out.append([s[i], j - i])
i = j
return out
a, b = runs(name), runs(typed)
if len(a) != len(b):
return False
for (ca, na), (cb, nb) in zip(a, b):
if ca != cb or nb < na:
return False
return Trueclass Solution {
public:
bool isLongPressedName(string name, string typed) {
vector<pair<char, int>> a = runs(name), b = runs(typed);
if (a.size() != b.size()) return false;
for (size_t k = 0; k < a.size(); k++) {
if (a[k].first != b[k].first || b[k].second < a[k].second) return false;
}
return true;
}
private:
vector<pair<char, int>> runs(const string& s) {
vector<pair<char, int>> out;
size_t i = 0;
while (i < s.size()) {
size_t j = i;
while (j < s.size() && s[j] == s[i]) j++;
out.push_back({s[i], (int)(j - i)});
i = j;
}
return out;
}
};function isLongPressedName(name, typed) {
const runs = (s) => {
const out = [];
let i = 0;
while (i < s.length) {
let j = i;
while (j < s.length && s[j] === s[i]) j++;
out.push([s[i], j - i]);
i = j;
}
return out;
};
const a = runs(name), b = runs(typed);
if (a.length !== b.length) return false;
for (let k = 0; k < a.length; k++) {
if (a[k][0] !== b[k][0] || b[k][1] < a[k][1]) return false;
}
return true;
}2Optimal (two pointers)
O(n + m)Each index only moves forward.O(1)Two indices.Walk through typed with index j while i points at the next unmatched character of name. A typed character is fine if it matches name[i] (advance both) or if it repeats the previous typed character (a long press, advance only j). Anything else is a wrong key. At the end every name character must be matched.
- i = 0. For j from 0 to typed.length - 1:
- If i < name.length and typed[j] == name[i], i++.
- Else if j > 0 and typed[j] == typed[j - 1], it is a long press: continue.
- Else return false.
- Return i == name.length.
class Solution {
public boolean isLongPressedName(String name, String typed) {
int i = 0;
for (int j = 0; j < typed.length(); j++) {
if (i < name.length() && typed.charAt(j) == name.charAt(i)) i++;
else if (j > 0 && typed.charAt(j) == typed.charAt(j - 1)) continue;
else return false;
}
return i == name.length();
}
}class Solution:
def isLongPressedName(self, name: str, typed: str) -> bool:
i = 0
for j in range(len(typed)):
if i < len(name) and typed[j] == name[i]:
i += 1
elif j > 0 and typed[j] == typed[j - 1]:
continue
else:
return False
return i == len(name)class Solution {
public:
bool isLongPressedName(string name, string typed) {
size_t i = 0;
for (size_t j = 0; j < typed.size(); j++) {
if (i < name.size() && typed[j] == name[i]) i++;
else if (j > 0 && typed[j] == typed[j - 1]) continue;
else return false;
}
return i == name.size();
}
};function isLongPressedName(name, typed) {
let i = 0;
for (let j = 0; j < typed.length; j++) {
if (i < name.length && typed[j] === name[i]) i++;
else if (j > 0 && typed[j] === typed[j - 1]) continue;
else return false;
}
return i === name.length;
}Edge cases to test
- Identical strings (true)
- typed shorter than name (always false)
- Extra characters after the whole name was matched
- The first character of typed differs from name
- A run in typed that is shorter than the matching run in name
Hints
Hint 1
Split both strings into runs of equal letters, e.g. aabccc is (a,2) (b,1) (c,3).
Hint 2
Holding a key can only make a run longer, never shorter, and can never create or remove a run.
Hint 3
You can do the same check with two indices, without building the runs: each typed character either matches the next name character or repeats the previous typed character.
FAQ
What is the best time complexity for Long Pressed Name?
Optimal (two pointers) runs in O(n + m) time and O(1) extra space. Each index only moves forward.
Which pattern does Long Pressed Name use?
It is a arrays & hashing problem that uses the two pointer pattern. Other problems with the same pattern: Two Sum II - Input Array Is Sorted, Valid Triangle Number, Container With Most Water.
Is there a brute force solution for Long Pressed Name?
Yes. Brute force (compare run-length groups) takes O(n + m) time and O(n + m) space. Encode both strings as lists of (letter, count) runs.
Which edge cases should I test for Long Pressed Name?
Identical strings (true); typed shorter than name (always false); Extra characters after the whole name was matched; The first character of typed differs from name; A run in typed that is shorter than the matching run in name.