Long Pressed Name

Difficulty: Easy | Acceptance: 32.90% | Paid: No Topics: Two Pointers, String

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

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 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.

• Examples
• Constraints
• Two Pointers
• Grouping / Run-Length Encoding

Examples

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 have been long pressed, but it is not present in typed.

Example 3:

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

Constraints

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

Two Pointers

Intuition We can iterate through both strings simultaneously using two pointers. If the characters match, we move both pointers forward. If they don’t match, we check if the current character in typed is a long-pressed repeat of the previous character; if so, we skip it. Otherwise, the strings are incompatible.

Steps

• Initialize two pointers, i for name and j for typed, both starting at 0.
• Iterate while j is within the bounds of typed.
• If i is within bounds and name[i] matches typed[j], increment both pointers.
• Else, if j is greater than 0 and typed[j] matches the previous character typed[j-1], increment j to skip the long-pressed character.
• If neither condition is met, return false.
• After the loop, return true only if i has reached the end of name.

class Solution:
    def isLongPressedName(self, name: str, typed: str) -> bool:
        i = 0
        for j in range(len(typed)):
            if i < len(name) and name[i] == typed[j]:
                i += 1
            elif j == 0 or typed[j] != typed[j-1]:
                return False
        return i == len(name)

Complexity

• Time: O(N + M), where N and M are the lengths of name and typed. We traverse each string at most once.
• Space: O(1), we only use a few variables for pointers.
• Notes: This is the most optimal approach in terms of both time and space.

Grouping / Run-Length Encoding

Intuition We can break both strings down into groups of consecutive identical characters (e.g., “aaleex” becomes [(a, 2), (l, 1), (e, 2), (x, 1)]). We then compare these groups one by one. The characters must match, and the count in typed must be greater than or equal to the count in name.

Steps

• Define a helper function to generate a list of groups (character, count) for a string.
• Generate groups for name and typed.
• If the number of groups differs, return false.
• Iterate through the corresponding groups of both strings.
• If the characters differ, or if the count in typed is less than the count in name, return false.
• If all checks pass, return true.

class Solution:
    def isLongPressedName(self, name: str, typed: str) -> bool:
        def get_groups(s):
            groups = []
            i = 0
            while i < len(s):
                j = i
                while j < len(s) and s[j] == s[i]:
                    j += 1
                groups.append((s[i], j - i))
                i = j
            return groups
        
        g1 = get_groups(name)
        g2 = get_groups(typed)
        
        if len(g1) != len(g2):
            return False
            
        for (c1, n1), (c2, n2) in zip(g1, g2):
            if c1 != c2 or n2 < n1:
                return False
                
        return True

Complexity

• Time: O(N + M), where N and M are the lengths of name and typed. We traverse each string to build groups and then traverse the groups.
• Space: O(N + M) in the worst case to store the groups for both strings (e.g., if all characters are unique).
• Notes: This approach uses more memory than the Two Pointers method but can be more intuitive to understand as it explicitly separates the character counts.