925. Long Pressed Name

LeetCode Problem Link (opens new window)

Your friend is typing their name into a keyboard. Sometimes, when typing a character c, the key might get long-pressed, and the character might be typed one or more times.

You will check the typed characters typed and determine if it could be your friend's name with some characters possibly long-pressed, then return True.

Example 1:

• Input: name = "alex", typed = "aaleex"
• Output: true
• Explanation: 'a' and 'e' in 'alex' were long pressed.

Example 2:

• Input: name = "saeed", typed = "ssaaedd"
• Output: false
• Explanation: 'e' must be typed twice but it wasn't in the typed output.

Example 3:

• Input: name = "leelee", typed = "lleeelee"
• Output: true

Example 4:

• Input: name = "laiden", typed = "laiden"
• Output: true
• Explanation: It's not necessary to long press any characters.

Thought Process

Initially, this problem might seem to involve hashing, but a closer inspection reveals that order must be preserved.

Therefore, we can simultaneously iterate over both strings, name and typed, comparing them.

Key points to consider during comparison:

• If name[i] and typed[j] are the same, then increment both i++ and j++ (proceed to the next comparison).
• If name[i] and typed[j] are different:
  • Check if they differ at the first character, i.e., if j == 0, then immediately return false.
  • If they don’t differ at the first character, skip over repeating characters in typed by advancing j, and compare name[i] and typed[j] again:
    • If they are the same, then increment both i++ and j++ (proceed to the next comparison).
    • If they are different, return false.

After comparing, there are two possibilities:

• The name has unmatched characters left, e.g., name:"pyplrzzzzdsfa" typed:"ppyypllr".
• The typed has unmatched characters left, e.g., name:"alex" typed:"alexxrrrrssda".

Animation below:

Thinking through the logic above makes it easy to write the following C++ code:

class Solution {
public:
    bool isLongPressedName(string name, string typed) {
        int i = 0, j = 0;
        while (i < name.size() && j < typed.size()) {
            if (name[i] == typed[j]) { // If same, proceed to match next characters
                j++; i++;
            } else { // If different
                if (j == 0) return false; // If differ at first character, return false
                // Skip duplicate characters in `typed` and prevent `j` from going out of bounds
                while(j < typed.size() && typed[j] == typed[j - 1]) j++;
                if (name[i] == typed[j]) { // After skipping, match `name[i]` with `typed[j]`
                    j++; i++; // If same, proceed to match next characters
                }
                else return false;
            }
        }
        // Indicates unmatched characters remain in `name`, e.g., `name:"pyplrzzzzdsfa"` `typed:"ppyypllr"`
        if (i < name.size()) return false;

        // Indicates unmatched characters remain in `typed`, e.g., `name:"alex"` `typed:"alexxrrrrssda"`
        while (j < typed.size()) {
            if (typed[j] == typed[j - 1]) j++;
            else return false;
        }
        return true;
    }
};

Time Complexity: O(n)
Space Complexity: O(1)

Other Language Versions

Java

class Solution {
    public boolean isLongPressedName(String name, String typed) {
        int i = 0, j = 0;
        int m = name.length(), n = typed.length();
        while (i< m && j < n) {
            if (name.charAt(i) == typed.charAt(j)) {  // If same, proceed to match next characters
                i++; j++;
            }
            else {
                if (j == 0) return false; // If differ at first character, return false
                // Check boundary at n-1 to prevent out of bounds, e.g., `name:"kikcxmvzi"` `typed:"kiikcxxmmvvzzz"`
                while (j < n-1 && typed.charAt(j) == typed.charAt(j-1)) j++;
                if (name.charAt(i) == typed.charAt(j)) {  // After skipping, match `name[i]` with `typed[j]`
                    i++; j++; // If same, proceed to match next characters
                }
                else return false;
            }
        }
        // Indicates unmatched characters remain in `name`
        if (i < m) return false;
        // Indicates unmatched characters remain in `typed`
        while (j < n) {
            if (typed.charAt(j) == typed.charAt(j-1)) j++;
            else return false;
        }
        return true;
    }
}

Python

        i = j = 0
        while(i<len(name) and j<len(typed)):
        # If the current letter matches, move as far as possible
            if typed[j]==name[i]:
                while j+1<len(typed) and typed[j]==typed[j+1]:
                    j+=1
                    # special case when there are consecutive repeating letters
                    if i+1<len(name) and name[i]==name[i+1]:
                        i+=1
                else:
                    j+=1
                    i+=1
            else:
                return False
        return i == len(name) and j==len(typed)

Go

func isLongPressedName(name string, typed string) bool {
    if(name[0] != typed[0] || len(name) > len(typed)) {
        return false;
    }

    idx := 0 // index for `name`
    var last byte  // last matched character
    for i := 0; i < len(typed); i++ {
        if idx < len(name) && name[idx] == typed[i] {
            last = name[idx]
            idx++
        } else if last == typed[i] {
            continue
        } else  {
            return false
        }
    }
    return idx == len(name)
}

JavaScript：

var isLongPressedName = function(name, typed) {
    let i = 0, j = 0;
    const m = name.length, n = typed.length;
    while(i < m && j < n){
        if(name[i] === typed[j]){ // If same, proceed to match next characters
            i++; j++;
        } else {
            if(j === 0) return false; // If differ at first character, return false
            // Check boundary at n-1 to prevent out of bounds, e.g., `name:"kikcxmvzi"` `typed:"kiikcxxmmvvzzz"`
            while(j < n - 1 && typed[j] === typed[j-1]) j++;
            if(name[i] === typed[j]){ // After skipping, match `name[i]` with `typed[j]`, proceed if same
                i++; j++;
            } else {
                return false;
            }
        }
    }
    // Indicates unmatched characters remain in `name`, e.g., `name:"pyplrzzzzdsfa"` `typed:"ppyypllr"`
    if(i < m) return false;
    // Indicates unmatched characters remain in `typed`, e.g., `name:"alex"` `typed:"alexxrrrrssda"`
    while(j < n) {
        if(typed[j] === typed[j-1]) j++;
        else return false;
    }
    return true;
};

TypeScript

function isLongPressedName(name: string, typed: string): boolean {
    const nameLength: number = name.length,
        typeLength: number = typed.length;
    let i: number = 0,
        j: number = 0;
    while (i < nameLength && j < typeLength) {
        if (name[i] !== typed[j]) return false;
        i++;
        j++;
        if (i === nameLength || name[i] !== name[i - 1]) {
            // Skip consecutive same characters in `typed`
            while (j < typeLength && typed[j] === typed[j - 1]) {
                j++;
            }
        }
    }
    return i === nameLength && j === typeLength;
};