Problem Description

The "Long Pressed Name" problem asks you to determine whether a string typed could be a result of someone typing another string name with possible long presses on some keys. A long press means a character in name could appear one or more times consecutively in typed, but the order and sequence of characters must match name.

Constraints:

• Both name and typed are non-empty strings consisting of lowercase English letters.
• Characters in typed must appear in the same order as in name.
• Each character in typed may correspond to one or more of the same character in name (long press), but not to a different character.
• Do not "reuse" characters from name for different positions in typed.

Thought Process

At first glance, you might think to compare name and typed character by character. However, since long presses are allowed, the same character in name can appear multiple times consecutively in typed. This means we need a way to "skip over" repeated characters in typed as long as they match the current character in name.

A brute-force approach would try all possible ways to map name to typed, but that's inefficient. Instead, a two-pointer technique is suitable: one pointer for name, and one for typed. We move through both strings, advancing the pointer in typed as long as we see valid long presses, and only advance the pointer in name when we see a match.

The key insight is to ensure all characters in name are matched in order, and any extra repeated characters in typed are just valid long presses of the current character.

Solution Approach

The optimal solution uses two pointers, i for name and j for typed:

1. Initialize both pointers at 0.
2. While j is less than the length of typed:
   • If name[i] equals typed[j], it’s a match. Advance both pointers.
   • If typed[j] is the same as typed[j-1] (i.e., a long press of the previous character), advance j only.
   • Otherwise, return false (the characters don't match and it's not a valid long press).
3. After the loop, check if i has reached the end of name. If not, some characters in name were not matched, so return false.
4. If all conditions are satisfied, return true.

This approach ensures that:

• Every character in name is accounted for in typed in order.
• Extra characters in typed are only allowed if they are repeated long presses of the previous character.

Example Walkthrough

Example:
name = "alex", typed = "aaleex"

1. i=0, j=0: name[0]='a', typed[0]='a' (match, advance both)
2. i=1, j=1: name[1]='l', typed[1]='a' (not match, but typed[1]==typed[0]: long press, advance j)
3. i=1, j=2: name[1]='l', typed[2]='l' (match, advance both)
4. i=2, j=3: name[2]='e', typed[3]='e' (match, advance both)
5. i=3, j=4: name[3]='x', typed[4]='e' (not match, but typed[4]==typed[3]: long press, advance j)
6. i=3, j=5: name[3]='x', typed[5]='x' (match, advance both)
7. i=4, j=6: i has reached the end of name; success!

The output is true because every character in name is matched in order, and extra characters in typed are valid long presses.

Time and Space Complexity

Brute-force approach: Trying all possible mappings would have exponential time complexity and is not feasible for longer strings.

Optimized (two-pointer) approach:

• Time complexity: O(n + m), where n is the length of name and m is the length of typed. Each pointer moves forward at most once per character.
• Space complexity: O(1), because we only use a constant number of pointers and variables.

Summary

The "Long Pressed Name" problem is efficiently solved using a two-pointer technique. By carefully comparing characters and allowing for valid long presses, we ensure that typed is a possible result of typing name. The approach is both intuitive and optimal, using linear time and constant space, making it suitable for large inputs. The key insight is to recognize and correctly handle repeated characters as legitimate long presses.

Code Implementation

class Solution:
    def isLongPressedName(self, 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)
    

class Solution {
public:
    bool isLongPressedName(string name, string typed) {
        int 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();
    }
}
    

var isLongPressedName = function(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;
};