Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The alphabet contains only a, b, and c, so a balanced substring uses one, two, or three distinct characters. Handle these cases separately. Equal prefix-count differences identify substrings where the participating characters occur equally often.

Approach

For one character, find the longest contiguous equal-character run. For each two-character pair, scan only blocks that exclude the third character. Within a block, track the count difference between the pair and store its earliest index, starting with difference zero just before the block. Repeating a difference gives equal positive counts in the intervening nonempty substring. Reset at each excluded character.

For all three characters, scan the whole string while tracking (countA - countB, countB - countC). Equal pairs at two prefix endpoints mean the intervening counts of all three characters are equal. Store only the earliest occurrence of each state to maximize the resulting length.

Return the maximum across all cases. Splitting by the number of present characters ensures every balanced substring is covered while preventing zero counts of absent characters from being mistaken for required occurrences.

class Solution:
    def longestBalanced(self, s: str) -> int:
        n = len(s)
        res = 0

        # one char
        i = 0
        while i < n:
            j = i
            while j < n and s[j] == s[i]:
                j += 1
            res = max(res, j - i)
            i = j

        # two chars
        def two(x, y, exclude):
            i = 0
            mx = 0

            while i < n:
                if s[i] == exclude:
                    i += 1
                    continue
                m = {0: i - 1}
                cx, cy = 0, 0
                while i < n and s[i] != exclude:
                    if s[i] == x:
                        cx += 1
                    else:
                        cy += 1
                    key = cx - cy
                    if key in m:
                        mx = max(mx, i - m[key])
                    else:
                        m[key] = i
                    i += 1

            return mx

        res = max(res, two('a', 'b', 'c'))
        res = max(res, two('a', 'c', 'b'))
        res = max(res, two('b', 'c', 'a'))

        # three chars
        m = {(0, 0): -1}
        ca, cb, cc = 0, 0, 0

        for i in range(n):
            if s[i] == 'a':
                ca += 1
            elif s[i] == 'b':
                cb += 1
            else:
                cc += 1
            key = (ca - cb, cb - cc)
            if key in m:
                res = max(res, i - m[key])
            else:
                m[key] = i

        return res

Complexity analysis

Let n = s.length. Time: O(n). Auxiliary space: O(n) for earliest-prefix maps.