We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Long Pressed Name

Number: 961

Difficulty: Easy

Paid? No

Companies: LinkedIn, Google, Adobe

Problem Description

Given two strings, name and typed, determine if typed could be produced by long pressing some keys while typing name. In other words, check if typed can be formed by repeating some characters in name consecutively.

Key Insights

  • Use two pointers to traverse both strings simultaneously.
  • When characters match, advance both pointers.
  • If the current characters do not match, check if the current typed character is a repetition (long press) of the previous character.
  • Ensure that every character in name appears in the correct order in typed.

Space and Time Complexity

Time Complexity: O(n + m), where n is the length of name and m is the length of typed. Space Complexity: O(1)

Solution

We solve the problem using the two pointers approach. One pointer iterates through name while the other iterates through typed. At each step:

  1. If the characters at both pointers match, move both pointers ahead.
  2. If they do not match, check if the current character in typed is the same as the previous character in typed (indicating a long press), and then move the typed pointer.
  3. If neither condition holds, return False. Finally, if we have traversed the entire name, the typed input is a valid long pressed version; otherwise, return False.

Code Solutions

# Define a function to check for long pressed name
def isLongPressedName(name, typed):
    name_ptr = 0  # Pointer for the 'name' string
    typed_ptr = 0  # Pointer for the 'typed' string

    # Loop through the typed string
    while typed_ptr < len(typed):
        # If characters match, move both pointers forward
        if name_ptr < len(name) and name[name_ptr] == typed[typed_ptr]:
            name_ptr += 1
            typed_ptr += 1
        # If not a direct match, check if it is a long press of the previous character
        elif typed_ptr > 0 and typed[typed_ptr] == typed[typed_ptr - 1]:
            typed_ptr += 1
        else:
            # Mismatch that cannot be explained by a long press
            return False
    # Check if all characters in the 'name' have been matched
    return name_ptr == len(name)

# Example usage:
print(isLongPressedName("alex", "aaleex"))  # Expected output: True
print(isLongPressedName("saeed", "ssaaedd"))  # Expected output: False
← Back to All Questions