Approach #1: Run Length Encoding [Accepted]
Intuition
For some word, write the head character of every group, and the count of that group. For example, for "abbcccddddaaaaa"
, we'll write the "key" of "abcda"
, and the "count" [1,2,3,4,5]
.
Let's see if a word
is stretchy. Evidently, it needs to have the same key as S
.
Now, let's say we have individual counts c1 = S.count[i]
and c2 = word.count[i]
.

If
c1 < c2
, then we can't make thei
th group ofword
equal to thei
th word ofS
by adding characters. 
If
c1 >= 3
, then we can add letters to thei
th group ofword
to match thei
th group ofS
, as the latter is extended. 
Else, if
c1 < 3
, then we must havec2 == c1
for thei
th groups ofword
andS
to match.
Complexity Analysis

Time Complexity: , where is the length of
words
(at least 1), and is the maximum length of a word. 
Space Complexity: .
Analysis written by: @awice.