Solution
Approach 1: Group into Blocks
Intuition and Algorithm
For a string like S = 'aabbbbccc'
, we can group it into blocks groupify(S) = [('a', 2), ('b', 4), ('c', 3)]
, that consist of a key 'abc'
and a count [2, 4, 3]
.
Then, the necessary and sufficient condition for typed
to be a longpressed version of name
is that the keys are the same, and each entry of the count of typed
is at least the entry for the count of name
.
For example, 'aaleex'
is a longpressed version of 'alex'
: because when considering the groups [('a', 2), ('l', 1), ('e', 2), ('x', 1)]
and [('a', 1), ('l', 1), ('e', 1), ('x', 1)]
, they both have the key 'alex'
, and the count [2,1,2,1]
is at least [1,1,1,1]
when making an elementbyelement comparison (2 >= 1, 1 >= 1, 2 >= 1, 1 >= 1)
.
Complexity Analysis

Time Complexity: , where are the lengths of
name
andtyped
. 
Space Complexity: .
Approach 2: Two Pointer
Intuition
As in Approach 1, we want to check the key and the count. We can do this on the fly.
Suppose we read through the characters name
, and eventually it doesn't match typed
.
There are some cases for when we are allowed to skip characters of typed
. Let's use a tuple to denote the case (name
, typed
):

In a case like
('aab', 'aaaaab')
, we can skip the 3rd, 4th, and 5th'a'
intyped
because we have already processed an'a'
in this block. 
In a case like
('a', 'b')
, we can't skip the 1st'b'
intyped
because we haven't processed anything in the current block yet.
Algorithm
This leads to the following algorithm:
 For each character in
name
, if there's a mismatch with the next character intyped
: If it's the first character of the block in
typed
, the answer isFalse
.  Else, discard all similar characers of
typed
coming up. The next (different) character coming must match.
 If it's the first character of the block in
Also, we'll keep track on the side of whether we are at the first character of the block.
Complexity Analysis

Time Complexity: , where are the lengths of
name
andtyped
. 
Space Complexity: in additional space complexity. (In Java,
.toCharArray
makes this , but this can be easily remedied.)
Analysis written by: @awice.