Long Pressed Name

easy two pointers string

Problem

Your friend is typing their name on a keyboard. Sometimes, when typing a character, the key may get long pressed, and the character will be typed one or more times. You examine the typed characters of the keyboard. Given the string name (their intended name) and the string typed, return true if it is possible that it was your friend's name with some characters long pressed.

Inputname = "alex", typed = "aaleex"

Outputtrue

'a' and 'e' were long pressed; every group in typed matches name with a count that is at least as large.

name

typed

def is_long_pressed_name(name, typed):
    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)

function isLongPressedName(name, typed) {
  let i = 0, j = 0;
  while (j < typed.length) {
    if (i < name.length && name[i] === typed[j]) {
      i++;
      j++;
    } else if (j > 0 && typed[j] === typed[j - 1]) {
      j++;
    } else {
      return false;
    }
  }
  return i === name.length;
}

class Solution {
    public 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();
    }
}

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();
}

Explanation

A long press just means a key got held down, so some letters in typed repeat extra times. We walk both strings together with two pointers, i over name and j over typed, deciding what each character of typed is.

If name[i] equals typed[j], it is a real matched character, so advance both pointers. If not, the only acceptable explanation is that typed[j] is a repeat of the previous typed character (a long press): check typed[j] == typed[j-1] and, if so, advance only j.

If a character of typed is neither the next needed letter nor a repeat, it cannot be explained, so we return false right away.

After consuming all of typed, we must also confirm i reached the end of name — otherwise some required letters were never typed. Only then is the answer true.

Example: name = "alex", typed = "aaleex". We match a, then the second a is a long press, match l, match e, the extra e is a long press, match x. Everything is explained and i finished, so true.

Time: O(m + n) Space: O(1)