algoadvance

The problem is taken from LeetCode and is stated as follows:

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

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 wasn’t in the typed output.

Example 3:

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

Explanation: ‘e’ was long pressed in both places it appears in ‘leelee’.

Example 4:

Input: name = "laiden", typed = "laiden"
Output: True

Explanation: No characters are long pressed.

Constraints:

Clarifying Questions

  1. What happens if typed is shorter than name?
    • Typed cannot represent the name, and we should return False.
  2. Can we assume all characters in name and typed are lowercase letters?
    • Yes, according to the problem constraints.

Strategy

We will use a two-pointer technique to solve this problem. Here’s the detailed strategy:

  1. Initialize two pointers, i for name and j for typed.
  2. Traverse through typed using pointer j:
    • If name[i] == typed[j], move both pointers i and j.
    • If typed[j] == typed[j-1], just move pointer j (long press scenario).
    • If neither of the above conditions is met, return False.
  3. At the end of traversal of typed, if i has traversed all of name, return True.
  4. Else, return False.

Code

def isLongPressedName(name: str, typed: str) -> bool:
    i, j = 0, 0
    while j < len(typed):
        if i < len(name) and name[i] == typed[j]:
            i += 1
        elif j > 0 and typed[j] == typed[j - 1]:
            j += 1
            continue
        else:
            return False
        j += 1

    return i == len(name)

# Example usage:
print(isLongPressedName("alex", "aaleex"))      # Output: True
print(isLongPressedName("saeed", "ssaaedd"))    # Output: False
print(isLongPressedName("leelee", "lleeelee"))  # Output: True
print(isLongPressedName("laiden", "laiden"))    # Output: True

Time Complexity

The time complexity of this solution is (O(n + m)), where (n) is the length of name and (m) is the length of typed. This is because we are traversing both strings in linear time using two pointers.

Try our interview co-pilot at AlgoAdvance.com