Long Pressed Name

Easy
510.

Long Pressed Name

Long Pressed Name is an easy coding problem on strings and two pointers, asked in Amazon and Google interviews.

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 <= 1000
  • Both strings consist of lowercase English letters only.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} name
 * @param {string} typed
 * @return {boolean}
 */
var isLongPressedName = function(name, typed) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 1000
  • Both strings consist of lowercase English letters only.

Hints for Long Pressed Name

  1. Hint 1

    Walk both strings with two pointers, matching characters as they line up.

  2. Hint 2

    When they differ, the only legal explanation is that the current typed character repeats the previous one.

  3. Hint 3

    At the end, every character of name must 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

  1. Set i into name and j into typed, both at 0.
  2. If name[i] == typed[j], advance both.
  3. Otherwise, if typed[j] equals typed[j-1], it is a long-press artefact — advance j only.
  4. Otherwise return false.
  5. After the loop return i == name.length to confirm every character of name was 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.length check accepts name = "alex", typed = "aaleexa"… and worse, accepts a typed that ran out early.
  • Comparing against typed[j-1] requires j > 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