# Long Pressed Name
**Difficulty:** EASY
[External](https://leetcode.com/problems/long-pressed-name)
Canonical: https://scaleengineer.com/dsa/problems/long-pressed-name
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** String
---
## 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.

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

# Approaches
## Group and Compare
This approach involves compressing both the `name` and `typed` strings into a sequence of character groups. Each group consists of a character and its consecutive count. We then compare these two sequences of groups to determine if `typed` could be a long-pressed version of `name`.
**Time:** O(M + N), where M is the length of `name` and N is the length of `typed`. This is because we iterate through both strings once to create the groups and then iterate through the groups. · **Space:** O(M + N). In the worst case (e.g., a string with no consecutive characters like 'abcdef'), the space required to store the groups is proportional to the length of the strings, where M and N are the lengths of `name` and `typed` respectively.
**Pros:** The logic is quite clear and directly models the problem of comparing blocks of characters.; It separates the concern of parsing the strings from comparing them, which can make the code easier to read and debug.
**Cons:** Requires extra space proportional to the lengths of the strings, which can be significant for large inputs.; Involves creating intermediate data structures (lists of groups), which adds overhead compared to an in-place approach.
### Explanation
The core idea is to represent each string by its blocks of identical consecutive characters. For example, `name = "saeed"` becomes `[('s', 1), ('a', 1), ('e', 2), ('d', 1)]` and `typed = "ssaaedd"` becomes `[('s', 2), ('a', 2), ('e', 1), ('d', 2)]`.

For `typed` to be a valid long-pressed version of `name`, two conditions must be met:
1. The sequence of characters in both compressed forms must be identical. For instance, `name="ab"` and `typed="ac"` is invalid because the character sequence `a,b` is different from `a,c`.
2. For each corresponding character group, the count in `typed` must be greater than or equal to the count in `name`. A character cannot appear fewer times in `typed` than in `name`.

The algorithm proceeds by first creating these grouped representations for both strings and then comparing them based on the rules above.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    // A simple class to hold a character and its consecutive count.
    class CharGroup {
        char character;
        int count;
        CharGroup(char character, int count) {
            this.character = character;
            this.count = count;
        }
    }

    public boolean isLongPressedName(String name, String typed) {
        List<CharGroup> nameGroups = getGroups(name);
        List<CharGroup> typedGroups = getGroups(typed);

        if (nameGroups.size() != typedGroups.size()) {
            return false;
        }

        for (int i = 0; i < nameGroups.size(); i++) {
            if (nameGroups.get(i).character != typedGroups.get(i).character ||
                nameGroups.get(i).count > typedGroups.get(i).count) {
                return false;
            }
        }
        return true;
    }

    private List<CharGroup> getGroups(String s) {
        List<CharGroup> groups = new ArrayList<>();
        if (s.isEmpty()) return groups;
        int i = 0;
        while (i < s.length()) {
            char c = s.charAt(i);
            int count = 0;
            int j = i;
            while (j < s.length() && s.charAt(j) == c) {
                count++;
                j++;
            }
            groups.add(new CharGroup(c, count));
            i = j;
        }
        return groups;
    }
}
```
### Algorithm
- Define a helper function `getGroups(String s)` that compresses a string into a list of character-count groups.
- In `getGroups`, iterate through the string, identifying consecutive blocks of identical characters and counting them.
- Store each character and its count as a group in a list.
- In the main function, call `getGroups` for both `name` and `typed` strings.
- Compare the sizes of the resulting group lists. If they are not equal, return `false`.
- Iterate through both lists simultaneously. For each index `i`:
  - a. Check if the character of `nameGroups[i]` is the same as `typedGroups[i]`.
  - b. Check if the count of `nameGroups[i]` is greater than the count of `typedGroups[i]`.
  - c. If either check fails, return `false`.
- If the loop completes without returning, it means all conditions are met. Return `true`.

## Two-Pointer Traversal
A more efficient solution uses a two-pointer technique to traverse both strings simultaneously without creating any intermediate data structures. One pointer `i` tracks the position in `name`, and another pointer `j` tracks the position in `typed`.
**Time:** O(N), where N is the length of the `typed` string. We perform a single pass through the `typed` string. · **Space:** O(1). We only use a constant amount of extra space for the two pointers.
**Pros:** Highly efficient in both time and space.; It's an in-place algorithm that avoids the overhead of creating auxiliary data structures.
**Cons:** The logic with multiple conditions and pointer movements can be slightly more complex to reason about compared to the grouping approach.
### Explanation
This approach iterates through the `typed` string and tries to match its characters with the `name` string. The pointer `i` for `name` only advances when a character in `name` is successfully matched. The pointer `j` for `typed` always advances.

The logic handles three cases at each step of the traversal:
1. **Direct Match:** If `name[i]` and `typed[j]` are the same, it means we've found the next character of the name. We can advance both pointers `i` and `j`.
2. **Long Press:** If `name[i]` and `typed[j]` are different, we check if `typed[j]` is a 'long press' of the *previous* character in `name`. This is valid only if `typed[j]` is the same as `name[i-1]`. If it is, we only advance `j`, as we are consuming a repeated character in `typed`.
3. **Mismatch:** If neither of the above conditions is met, it means `typed[j]` is an invalid character that doesn't fit the sequence of `name`. We can immediately conclude that `typed` is not a valid long-pressed name and return `false`.

After the loop finishes (i.e., we've processed the entire `typed` string), we must also ensure that we have consumed the entire `name` string. If pointer `i` has reached the end of `name`, it's a valid match; otherwise, it's not.

```java
class Solution {
    public boolean isLongPressedName(String name, String typed) {
        int i = 0; // pointer for name
        int j = 0; // pointer for typed

        while (j < typed.length()) {
            if (i < name.length() && name.charAt(i) == typed.charAt(j)) {
                // Case 1: Direct match
                i++;
                j++;
            } else if (i > 0 && name.charAt(i - 1) == typed.charAt(j)) {
                // Case 2: Long press of the previous character
                j++;
            } else {
                // Case 3: Mismatch
                return false;
            }
        }

        // After iterating through typed, we must have consumed the entire name.
        return i == name.length();
    }
}
```
### Algorithm
- Initialize two pointers, `i = 0` for the `name` string and `j = 0` for the `typed` string.
- Loop while the `j` pointer is within the bounds of the `typed` string.
- Inside the loop, check for a match: if `i` is within the bounds of `name` and `name.charAt(i)` equals `typed.charAt(j)`, increment both `i` and `j`.
- If there's no direct match, check for a long press: if `i > 0` (to avoid index out of bounds) and `name.charAt(i-1)` equals `typed.charAt(j)`, increment only `j`.
- If neither of the above conditions is true, it's a mismatch. Return `false`.
- After the loop terminates, check if the `i` pointer has reached the end of the `name` string (`i == name.length()`). If it has, it means all characters of `name` were found in `typed` in the correct order. Return `true`. Otherwise, return `false`.

# Solutions
### Java

```java
class Solution {
public
  boolean isLongPressedName(String name, String typed) {
    int m = name.length(), n = typed.length();
    int i = 0, j = 0;
    for (; i < m && j < n; ++i, ++j) {
      if (name.charAt(i) != typed.charAt(j)) {
        return false;
      }
      int cnt1 = 0, cnt2 = 0;
      char c = name.charAt(i);
      while (i + 1 < m && name.charAt(i + 1) == c) {
        ++i;
        ++cnt1;
      }
      while (j + 1 < n && typed.charAt(j + 1) == c) {
        ++j;
        ++cnt2;
      }
      if (cnt1 > cnt2) {
        return false;
      }
    }
    return i == m && j == n;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool isLongPressedName(string name, string typed) {
    int m = name.size(), n = typed.size();
    int i = 0, j = 0;
    for (; i < m && j < n; ++i, ++j) {
      if (name[i] != typed[j])
        return false;
      int cnt1 = 0, cnt2 = 0;
      char c = name[i];
      while (i + 1 < m && name[i + 1] == c) {
        ++i;
        ++cnt1;
      }
      while (j + 1 < n && typed[j + 1] == c) {
        ++j;
        ++cnt2;
      }
      if (cnt1 > cnt2)
        return false;
    }
    return i == m && j == n;
  }
};

```

### Python

```python
class Solution:
    def isLongPressedName(self, name: str, typed: str) -> bool: m, n = len(name), len(typed) i = j = 0 while i < m and j < n: if name[i] != typed[j]: return False cnt1 = cnt2 = 0 c = name[i] while i + 1 < m and name[i + 1] == c: i += 1 cnt1 += 1 while j + 1 < n and typed[j + 1] == c: j += 1 cnt2 += 1 if cnt1 > cnt2: return False i, j = i + 1, j + 1 return i == m and j == n

```