Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A fancy string may retain at most two characters from every maximal run of equal letters. Keeping the first two from each run removes exactly the unavoidable excess and preserves separators between different runs.

Approach

Return strings of length at most two unchanged. Otherwise retain the first two characters and scan the remainder. Skip a character when it equals both immediately preceding characters in the original string; keep it otherwise. This drops every position after the second in each original run. Join the retained characters. Because at least one character survives from every run, removals never merge two separated same-letter runs into a new violation.

class Solution:
    def makeFancyString(self, s: str) -> str:
        n = len(s)

        if n <= 2:
            return s

        res = [s[0], s[1]]

        for i in range(2, n):
            if s[i] == s[i - 1] and s[i] == s[i - 2]:
                continue
            res.append(s[i])

        return "".join(res)

Complexity analysis

Let n = s.length. Time: O(n). Auxiliary space: O(n) for the output builder; the returned string also has length at most n.