Approach #1: Two Pointer [Accepted]
We scan through the string to identify the start and end of each group. If the size of the group is at least 3, we add it to the answer.
i, j with
i <= j. The
i pointer will represent the start of the current group, and we will increment
j forward until it reaches the end of the group.
We know that we have reached the end of the group when
j is at the end of the string, or
S[j] != S[j+1]. At this point, we have some group
[i, j]; and after, we will update
i = j+1, the start of the next group.
Time Complexity: , where is the length of
Space Complexity: , the space used by the answer.
Analysis written by: @awice.