Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A substring is balanced when all characters that actually occur in it have the same positive frequency. The smaller input permits checking every substring, while extending one right endpoint lets us update its counts incrementally.

Approach

For each starting index, create an empty frequency map. Move the ending index from that start to the end of the string, incrementing the newly included character's count. Convert the map's frequency values to a set. If this set has exactly one value, every present character has the same frequency, so update the longest length.

Return the largest qualifying length. Missing characters are not stored and therefore do not introduce zero counts into the equality check. Each start/end pair is examined once, and a single-character substring always qualifies, ensuring a valid baseline for a nonempty string.

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

        for i in range(n):
            fm = defaultdict(int)
            for j in range(i, n):
                fm[s[j]] += 1
                if len(set(fm.values())) == 1:
                    res = max(res, j - i + 1)

        return res

Complexity analysis

Let n = s.length and sigma be the alphabet size. Time: O(n^2 * sigma) (with a fixed small alphabet, O(n^2)). Auxiliary space: O(sigma).