Collapse adjacent duplicate characters

Question

Collapse every run of consecutive identical characters into a single copy of that character. Non-adjacent repeats are kept, so "aabbaa" becomes "aba", not "a".

"aaabbbccddd"  ->  "abcd"
"aabbaa"       ->  "aba"
""             ->  ""

Return the collapsed string in $O(n)$ time.

Accepted Answer

Walk the string once and append a character only when it differs from the last character you kept. That single comparison implicitly detects run boundaries: within a run the new character equals the last kept one and is skipped; at a boundary it differs and is appended. Build a list and join at the end. Tracing "aaabbbccddd": a is kept, the next two as match and are skipped, b differs and is kept, and so on, giving "abcd". For "aabbaa" the trailing aa differs from the kept b, so it becomes "aba", preserving the non-adjacent repeat. Time O(n), space O(n) for the output. Takeaway. "Keep it only…

Collapse adjacent duplicate characters

Your answer

More Coding questions