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 the ith group of word equal to the ith word of S by adding characters.

  • If c1 >= 3, then we can add letters to the ith group of word to match the ith group of S, as the latter is extended.

  • Else, if c1 < 3, then we must have c2 == c1 for the ith groups of word and S 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.