Long Pressed Name

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.

Constraints

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

Solution

The problem Long Pressed Name can be solved using two pointers to compare lengths of each sequences consisting of same characters. Let str = S(str, 1)S(str, 2)...S(str, n) where S(str, k) is a subseqeunce of str which contains all consecutive characters c that are different from S(str, k-1). Then, typed can be formed by long pressing some characters in name only when S(name, k).length <= S(typed, k).length holds true.

Implementation

static const int fast_io = []()
{
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    return 0;
}();

class Solution
{
  public:
    bool isLongPressedName(string name, string typed)
    {
        name.push_back(' ');
        typed.push_back(' ');

        int i, j;
        for (i = 0, j = 0; i < name.length() && j < typed.length(); i++, j++)
        {
            if (name[i] != typed[j])
                return false;

            if (name[i] != name[i + 1])
                while (typed[j] == typed[j + 1])
                    j += 1;
        }

        return i == name.length() && j == typed.length();
    }
};