Problem

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

You examine the typed characters of the keyboard. Return True if it is possible that it was your friends name, with some characters (possibly none) being long pressed.

Examples

Example 1

1
2
3

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

Example 2

1
2
3

Input: name = "saeed", typed = "ssaaedd"
Output: false
Explanation: 'e' must have been pressed twice, but it was not in the typed output.

Constraints

  • 1 <= name.length, typed.length <= 1000
  • name and typed consist of only lowercase English letters.

Solution

Method 1 – Two Pointers (1)

Intuition

We use two pointers to compare the name and typed strings. If the current characters match, move both pointers. If the current character in typed matches the previous character in typed, it’s a long press, so move the typed pointer. Otherwise, return false.

Approach

  1. Initialize two pointers, i for name and j for typed.
  2. While j is less than the length of typed:
    • If i is less than the length of name and name[i] == typed[j], increment both i and j.
    • Else if j > 0 and typed[j] == typed[j-1], increment j (long press).
    • Else, return false.
  3. After the loop, check if i has reached the end of name.
  4. Return true if so, otherwise false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    bool isLongPressedName(string name, string typed) {
        int i = 0, j = 0;
        while (j < typed.size()) {
            if (i < name.size() && name[i] == typed[j]) {
                i++; j++;
            } else if (j > 0 && typed[j] == typed[j-1]) {
                j++;
            } else {
                return false;
            }
        }
        return i == name.size();
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func isLongPressedName(name string, typed string) bool {
    i, j := 0, 0
    for j < len(typed) {
        if i < len(name) && name[i] == typed[j] {
            i++
            j++
        } else if j > 0 && typed[j] == typed[j-1] {
            j++
        } else {
            return false
        }
    }
    return i == len(name)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun isLongPressedName(name: String, typed: String): Boolean {
        var i = 0; var 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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def isLongPressedName(self, name: str, typed: str) -> bool:
        i = 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)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
    pub fn is_long_pressed_name(name: String, typed: String) -> bool {
        let (mut i, mut j) = (0, 0);
        let name = name.as_bytes();
        let typed = typed.as_bytes();
        while j < typed.len() {
            if i < name.len() && name[i] == typed[j] {
                i += 1;
                j += 1;
            } else if j > 0 && typed[j] == typed[j-1] {
                j += 1;
            } else {
                return false;
            }
        }
        i == name.len()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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

Complexity

  • ⏰ Time complexity: O(n + m), where n is the length of name and m is the length of typed. Each character is checked at most once.
  • 🧺 Space complexity: O(1), only a few pointers are used.