You are given a string s consisting of lowercase English letters.

A substring of s is called balanced if every distinct character that appears in the substring occurs the same number of times.

Your task is to return the length of the longest balanced substring of s.

A few points to clarify the problem:

• A substring is a contiguous, non-empty sequence of characters within the string. For example, the substrings of "abc" include "a", "ab", "bc", and "abc", but not "ac".
• A substring is balanced when all of its distinct characters share an identical frequency. For example:
  • "aabb" is balanced because both 'a' and 'b' appear exactly 2 times.
  • "abcabc" is balanced because 'a', 'b', and 'c' each appear exactly 2 times.
  • "aab" is not balanced because 'a' appears 2 times while 'b' appears only 1 time.
• Any substring consisting of a single character (e.g., "a") or repeated copies of one character (e.g., "aaa") is trivially balanced, since there is only one distinct character. This means the answer is always at least 1 for a non-empty string.

The goal is to examine all possible substrings of s and find the maximum length among those that satisfy the balanced condition.

A useful observation for checking balance: if a substring has v distinct characters and the maximum frequency of any character in it is mx, then the substring is balanced if and only if mx * v equals the substring's length j - i + 1. This works because the total length is the sum of all character frequencies; if every frequency were equal to the maximum mx, the total would be exactly mx * v — any character appearing fewer times would make the actual length smaller than mx * v.

The first thing to notice is that the "balanced" property depends on the exact frequency of every character in a substring, and this property does not behave nicely as a substring grows or shrinks — a balanced substring can become unbalanced by adding one character, and then become balanced again later. For example, "ab" is balanced, "aba" is not, but "abab" is balanced again. This non-monotonic behavior means classic techniques like a standard sliding window are hard to apply directly, because there is no simple condition telling us when to shrink the window.

Given that, the most natural strategy is brute-force enumeration of all substrings: fix a starting index i, then extend the ending index j one character at a time, and check whether s[i..j] is balanced at each step.

The key question becomes: how do we check the balanced condition efficiently as we extend j? Recounting all frequencies for every substring from scratch would cost an extra factor of time. Instead, we maintain the state incrementally:

• A counter cnt tracking the frequency of each character in the current window s[i..j]. Adding one character only requires a single update.
• v, the number of distinct characters — it increases by 1 exactly when a character's count goes from 0 to 1.
• mx, the maximum frequency among all characters — it can only stay the same or increase as we extend the window, so updating it is a single max operation.

Now comes the elegant observation that makes the check O(1). The length of the substring is the sum of all character frequencies. If there are v distinct characters and the largest frequency is mx, then:

• The total length is at most mx * v (each of the v characters appears at most mx times).
• The total length equals mx * v exactly when every distinct character appears precisely mx times — which is precisely the definition of balanced.

So instead of comparing all frequencies against each other, we simply test:

mx * v == j - i + 1

If this equation holds, the substring s[i..j] is balanced, and we update the answer with its length. This turns an expensive "are all counts equal?" check into a single multiplication and comparison, giving an overall O(n^2) solution with O(|Σ|) extra space, where |Σ| = 26 is the alphabet size.

Enumeration + Counting

Following the intuition, the implementation enumerates every possible starting position i of a substring in the range [0, ..., n-1]. For each fixed i, it extends the ending position j through the range [i, ..., n-1], maintaining the window's state incrementally as each new character s[j] joins the substring.

Data structures and variables:

• cnt: a hash table (Python's Counter) recording the frequency of each character in the current substring s[i..j]. Since s contains only lowercase English letters, it holds at most 26 entries.
• mx: the maximum frequency among all characters in the current substring.
• v: the number of distinct characters in the current substring.
• ans: the length of the longest balanced substring found so far.

Step-by-step walkthrough:

1. Outer loop — fix the start. For each starting index i, reset the state: create a fresh cnt, and set mx = 0 and v = 0. This guarantees the state describes only the current window s[i..j].

2. Inner loop — extend the end. For each ending index j from i to n - 1, absorb the character s[j]:

   • Increment its frequency: cnt[s[j]] += 1.
   • Update the maximum frequency: mx = max(mx, cnt[s[j]]). Only the newly added character could raise the maximum, so this single comparison suffices.
   • If cnt[s[j]] == 1, the character s[j] is appearing in this window for the first time, so increment the distinct-character count: v += 1.

3. Constant-time balance check. The substring s[i..j] has length j - i + 1. With v distinct characters each appearing at most mx times, the length can never exceed mx * v. Equality

   mx * v == j - i + 1

   holds exactly when every distinct character appears precisely mx times — i.e., the substring is balanced. When the check passes, update the answer:

   ans = max(ans, j - i + 1)

4. Return the result. After all pairs (i, j) have been examined, ans holds the length of the longest balanced substring.

Implementation:

class Solution:
    def longestBalanced(self, s: str) -> int:
        n = len(s)
        ans = 0
        for i in range(n):
            cnt = Counter()
            mx = v = 0
            for j in range(i, n):
                cnt[s[j]] += 1
                mx = max(mx, cnt[s[j]])
                if cnt[s[j]] == 1:
                    v += 1
                if mx * v == j - i + 1:
                    ans = max(ans, j - i + 1)
        return ans

Why the incremental updates are correct:

• mx never decreases while j grows for a fixed i, because characters are only added to the window — so comparing against the count of the latest character is enough.
• v only changes when a character's count transitions from 0 to 1, which is detected by cnt[s[j]] == 1 right after the increment.
• Both invariants hold precisely because the window only ever expands within the inner loop; the state is rebuilt from scratch whenever i advances.

Complexity analysis:

• Time complexity: O(n^2), where n is the length of s. There are O(n^2) pairs (i, j), and each inner-loop iteration performs only O(1) work thanks to the incremental updates and the mx * v check.
• Space complexity: O(|Σ|), where |Σ| = 26 is the size of the alphabet, used by the frequency table cnt.