A landscaping crew is preparing a hedge row for a topiary competition. The row is described left to right as a string of lowercase letters, where each letter names the shrub species planted at that spot. The competition rule is strict: after thinning, no three consecutive shrubs in the surviving row may belong to the same species. The crew wants to remove as few shrubs as possible while satisfying this rule, and the relative left-to-right order of the surviving shrubs must stay unchanged. Among all ways to remove the minimum number of shrubs, the crew always keeps a shrub unless keeping it would create a run of three identical consecutive species in what has been kept so far — i.e., scanning left to right, a shrub is discarded only when the two most recently kept shrubs already match its species. Report the row that remains after this minimum thinning.
A single line containing the string s, made only of lowercase English letters.
Print a single line: the resulting string after the minimum thinning described above.
Example 1
Input
aaabbbcc
Expected
aabbcc
Explanation
Scanning left to right: keep 'a','a' (2 a's), the 3rd 'a' would make three in a row so it is dropped; keep 'b','b', the 3rd 'b' is dropped for the same reason; both 'c's are kept since only two of them appear. The surviving row is "aabbcc".
Example 2
Input
aaabaaaa
Expected
aabaa
Explanation
Keep the first two 'a's ("aa"), drop the 3rd 'a', keep the 'b' ("aab"), keep the next two 'a's ("aabaa") — now the last two kept characters are 'a','a', so the remaining two 'a's in the row are both dropped. The surviving row is "aabaa".
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →