Problem Description

You have a friend who is typing their name into a keyboard. Sometimes when typing a character c, the key might get long pressed, meaning the character gets typed 1 or more times instead of just once.

Given two strings:

• name: the intended name your friend wanted to type
• typed: the actual characters that were typed on the keyboard

You need to determine if typed could have been produced by typing name with some characters being long pressed.

Return True if it's possible that typed was your friend's attempt at typing name (with potential long presses), and False otherwise.

For example:

• If name = "alex" and typed = "aaleex", this returns True because:

  • 'a' was typed once in name but twice in typed (long pressed)
  • 'l' was typed once in both
  • 'e' was typed once in name but twice in typed (long pressed)
  • 'x' was typed once in both

• If name = "saeed" and typed = "ssaaedd", this returns False because:

  • Although some characters are long pressed correctly, the final 'd' appears twice in typed but only once in name, and there's no second 'e' before it to match the pattern in name

The key insight is that every character in name must appear in typed in the same order, and each character group in typed must have at least as many occurrences as the corresponding group in name.

Intuition

To solve this problem, we need to think about what happens when someone types with potential long presses. The key observation is that the characters must appear in the exact same order in both strings, but in typed, each character can appear more times than in name due to long pressing.

Let's think about how we would manually check if typed could be derived from name:

1. We'd go through both strings character by character
2. For each character position in name, we'd check if it matches the current position in typed
3. Since long pressing means repeating the same character, we'd count consecutive occurrences of each character in both strings
4. The count in typed must be at least as much as in name (equal or more due to long pressing)

This naturally leads us to a two-pointer approach where we process groups of identical consecutive characters. For instance, if name has "aa" and typed has "aaaa", that's valid because we typed 'a' 4 times instead of 2 (long pressed). But if name has "aaa" and typed has "aa", that's invalid because we can't have fewer occurrences.

The algorithm emerges from this insight:

• Use pointer i for name and pointer j for typed
• At each step, if characters don't match, return False immediately
• Count consecutive identical characters starting from current positions in both strings
• If typed has fewer consecutive characters than name for any character group, it's impossible to produce typed from name
• Move both pointers to the next different character and repeat
• Finally, ensure we've consumed both strings completely

This approach efficiently validates whether each character group in typed could have been produced by typing the corresponding group in name with potential long presses.

Learn more about Two Pointers patterns.

Solution Approach

We implement the solution using a two-pointer technique to traverse both strings simultaneously while comparing character groups.

Step-by-step implementation:

1. Initialize pointers and lengths:

   • Set i = 0 and j = 0 to point to the start of name and typed respectively
   • Store lengths m = len(name) and n = len(typed) for boundary checking

2. Main traversal loop: While both pointers are within bounds (i < m and j < n):

   a. Character matching check:

   • If name[i] != typed[j], the characters don't match, return False

   b. Count consecutive characters in name:

   • Initialize x = i + 1
   • While x < m and name[x] == name[i], increment x
   • This gives us x - i occurrences of the current character in name

   c. Count consecutive characters in typed:

   • Initialize y = j + 1
   • While y < n and typed[y] == typed[j], increment y
   • This gives us y - j occurrences of the current character in typed

   d. Validate character group counts:

   • If x - i > y - j, it means typed has fewer occurrences than name
   • This is impossible with long pressing, so return False

   e. Move to next character groups:

   • Update i = x and j = y to point to the next different characters

3. Final validation:

   • After the loop, check if both strings have been completely traversed
   • Return i == m and j == n
   • This ensures we've processed all characters in both strings

Example walkthrough: For name = "alex" and typed = "aaleex":

• Compare 'a' groups: name has 1, typed has 2 ✓ (long pressed)
• Compare 'l' groups: both have 1 ✓
• Compare 'e' groups: name has 1, typed has 2 ✓ (long pressed)
• Compare 'x' groups: both have 1 ✓
• Both strings fully traversed, return True

The algorithm runs in O(m + n) time complexity where m and n are the lengths of the strings, as we traverse each string once. Space complexity is O(1) as we only use a constant amount of extra space.

Example Walkthrough

Let's walk through the algorithm with name = "alex" and typed = "aaleex":

Initial Setup:

• i = 0, j = 0 (pointers for name and typed)
• m = 4, n = 6 (lengths of strings)

Iteration 1: Processing 'a' groups

• Current characters: name[0] = 'a', typed[0] = 'a' ✓ (match)
• Count 'a' in name: Starting from i=0, we find 1 consecutive 'a' (stops at index 1)
• Count 'a' in typed: Starting from j=0, we find 2 consecutive 'a's (stops at index 2)
• Compare counts: name has 1, typed has 2 → Valid (2 ≥ 1, could be long pressed)
• Update pointers: i = 1, j = 2

Iteration 2: Processing 'l' groups

• Current characters: name[1] = 'l', typed[2] = 'l' ✓ (match)
• Count 'l' in name: 1 consecutive 'l' (stops at index 2)
• Count 'l' in typed: 1 consecutive 'l' (stops at index 3)
• Compare counts: both have 1 → Valid (1 ≥ 1)
• Update pointers: i = 2, j = 3

Iteration 3: Processing 'e' groups

• Current characters: name[2] = 'e', typed[3] = 'e' ✓ (match)
• Count 'e' in name: 1 consecutive 'e' (stops at index 3)
• Count 'e' in typed: 2 consecutive 'e's (stops at index 5)
• Compare counts: name has 1, typed has 2 → Valid (2 ≥ 1, could be long pressed)
• Update pointers: i = 3, j = 5

Iteration 4: Processing 'x' groups

• Current characters: name[3] = 'x', typed[5] = 'x' ✓ (match)
• Count 'x' in name: 1 consecutive 'x' (reaches end at index 4)
• Count 'x' in typed: 1 consecutive 'x' (reaches end at index 6)
• Compare counts: both have 1 → Valid (1 ≥ 1)
• Update pointers: i = 4, j = 6

Final Check:

• i = 4 = m (processed all of name)
• j = 6 = n (processed all of typed)
• Both strings fully traversed → Return True

The typed string "aaleex" could indeed be produced by typing "alex" with 'a' and 'e' being long pressed.

Solution Implementation

Time and Space Complexity

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

The algorithm uses two pointers i and j to traverse through both strings. In each iteration of the main while loop:

• We find consecutive occurrences of the same character in name starting from position i (advancing pointer x)
• We find consecutive occurrences of the same character in typed starting from position j (advancing pointer y)
• We then jump both pointers i and j to positions x and y respectively

Since each character in both strings is visited exactly once (either by the main pointers i/j or by the auxiliary pointers x/y), the total number of operations is proportional to m + n.

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space for the variables m, n, i, j, x, and y. No additional data structures are created that scale with the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Not Handling Trailing Characters in typed

The Problem: A common mistake is assuming that if we've processed all characters in name, we're done. However, typed might have extra characters at the end that don't correspond to any character in name.

Example:

• name = "alex"
• typed = "aaleexy"

Here, after matching "alex" with "aleex", there's an extra 'y' in typed. This should return False, but if we only check name_index == name_length without verifying that typed is also fully consumed, we might incorrectly return True.

Solution: Always verify both pointers have reached the end of their respective strings:

return name_index == name_length and typed_index == typed_length

Pitfall 2: Incorrect Character Group Comparison

The Problem: When comparing character groups, developers might accidentally compare individual characters instead of counting the entire group, leading to premature pointer advancement.

Incorrect approach:

# Wrong: This only compares one character at a time
while i < len(name) and j < len(typed):
    if name[i] == typed[j]:
        i += 1
        j += 1
    elif j > 0 and typed[j] == typed[j-1]:
        j += 1  # Skip long-pressed character
    else:
        return False

Why it fails: This approach doesn't properly handle cases where the same character appears in different positions in name. For example:

• name = "kikcxmvzi"
• typed = "kiikcxxmmvvzzi"

The incorrect approach might match the first 'k' in name with both 'k's in "kiik" of typed, causing misalignment.

Solution: Count and compare entire character groups before moving pointers:

# Count all consecutive occurrences of current character in name
next_name_index = name_index + 1
while next_name_index < name_length and name[next_name_index] == name[name_index]:
    next_name_index += 1

# Count all consecutive occurrences in typed
next_typed_index = typed_index + 1
while next_typed_index < typed_length and typed[next_typed_index] == typed[typed_index]:
    next_typed_index += 1

# Compare group counts
if (next_name_index - name_index) > (next_typed_index - typed_index):
    return False

Pitfall 3: Off-by-One Errors in Counting

The Problem: When counting consecutive characters, it's easy to make off-by-one errors by forgetting to include the current character in the count or by incorrectly initializing the counting pointer.

Incorrect:

# Wrong: Starting from current index instead of next
next_index = name_index  # Should be name_index + 1
while next_index < len(name) and name[next_index] == name[name_index]:
    next_index += 1

This would cause an infinite loop since name[name_index] == name[name_index] is always true.

Solution: Always start counting from the next position:

next_index = name_index + 1  # Start from the next character
while next_index < len(name) and name[next_index] == name[name_index]:
    next_index += 1
count = next_index - name_index  # This gives the correct count