925.long-pressed-name.md

925. Long Pressed Name

Hints

• Think about how to compare the characters in both strings while allowing extra repeated characters in typed.
• What happens when you encounter a character mismatch?
• What about when you have extra characters at the end?

Breakdowns

1. What to do when encountering the same character in both strings?

2. What to do when encountering a character mismatch?

3. How do you ensure both strings are fully processed?

• After processing all characters, both pointers should reach the end of their respective strings. If one finishes before the other, it indicates a mismatch.

Key Insights

The typed can have extra repeating characters compared to the name, but the sequence and minimal frequency of the characters must match name.

The key observation is that we can group consecutive identical characters and compare their counts. If name has more consecutive characters than typed for any group, it's invalid. This pattern appears in other problems like group by consecutive characters.

// Valid
name =  X, X       | Y, Y, Y       | Z
typed = X, X, X, X | Y, Y, Y, Y, Y | Z, Z, Z, Z, Z, Z, Z

// Invalid: charLen > typedLen
name =  X, X, X | Y, Y
typed = X, X    | Y

// Invalid: i != m at the end
name =  X, X       | Z
typed = X, X, X, X

// Invalid: j != n at the end
name =  X, X      
typed = X, X, X, X | Z

Two Pointers (Group by Consecutive)

The idea is to count the number of consecutive characters in the name and typed. If the number of consecutive characters in the name is greater than the number of consecutive characters in the typed, return false.

fun isLongPressedName(name: String, typed: String): Boolean {
    val m = name.length
    val n = typed.length
    var i = 0
    var j = 0
    while (i < m && j < n) {
        val char = name[i]
        if (char != typed[j]) return false

        // Count the number of consecutive characters in the name
        var iStart = i
        while (i + 1 < m && name[i] == name[i + 1]) {
            i++
        }
        val charLen = i - iStart + 1

        // Count the number of consecutive characters in the typed
        val jStart = j
        while (j + 1 < n && typed[j] == typed[j + 1]) {
            j++
        }
        val typedLen = j - jStart + 1

        if (charLen > typedLen) return false

        // i, j will stop at the last position of the consecutive characters, so we need to move to the next character for the next iteration.
        i++
        j++
    }
    return i == m && j == n
}

• Time Complexity: O(M + N), where M and N are the lengths of name and typed.
• Space Complexity: O(1).

Two Pointers (Two Sequences)

We can use two pointers to compare name and typed at the same time:

• Pointer i for name.
• Pointer j for typed.

At each step, we have 3 cases:

• If name[i] == typed[j], we move both pointers to the next character.
• Else if typed[j] == typed[j - 1], it's a long press, we move j only.
• Else, mismatch, return false.

fun isLongPressedName(name: String, typed: String): Boolean {
    val m = name.length
    val n = typed.length
    var i = 0
    var j = 0

    while (j < n) {
        if (i < m && name[i] == typed[j]) { // We have the same character at the two sequences
            i++
            j++
        } else if (0 < j && typed[j] == typed[j - 1]) { // It's a long press of name[i]
            j++
        } else { // Mismatch
            return false
        }
    }
    /**
     * We can't return true directly here, `name` have more characters than `typed`.
     *
     * Ex:
     * name = "ab"
     * typed = "a"
     * `b` in `name` was never matched.
     * We have to finish matching all characters in `name`.
     */
    return i == m
}

// Or equivalent, we can check `i < m OR j < n` in the while loop.
// The key difference is that we have to check the pointer is in bounds before accessing the character.
fun isLongPressedName(name: String, typed: String): Boolean {
    val m = name.length
    val n = typed.length
    var i = 0
    var j = 0

    /**
     * Here we use OR instead of AND. AND failed at the following case:
     * name = "a"
     * typed = "ax"
     * expected: false, actual: true
     */
    while (i < m || j < n) {
        if (i < m && j < n && name[i] == typed[j]) { // We have the same character at the two sequences
            i++
            j++
        } else if (0 < j && j < n && typed[j] == typed[j - 1]) { // It's a long press
            j++
        } else { // Mismatch
            return false
        }
    }
    /**
    * We can't return true directly here, `name` have more characters than `typed`.
    *
    * Ex:
    * name = "ab"
    * typed = "a"
    * `b` in `name` was never matched.
    * We have to finish matching all characters in `name`.
    */
    return i == m
}

• Time Complexity: O(N), where N is the length of typed.
• Space Complexity: O(1).

Edge Cases

• Extra different character at the beginning, in the middle, at the end in either name or typed.

Name	Typed
"a"	"ax"
"ax"	"a"

• Mismatch count of characters in name and typed.

Name	Typed
"abb"	"ab"

• Mismatch order: ab or `ba.

Pitfalls

• Not checking both pointers reach the end: Must ensure both i == m and j == n to confirm all characters are matched.
• Allowing character order changes: The sequence of characters must be preserved exactly.
• Not handling the case where typed is shorter than name: Need to check if name has unmatched characters.