Longest Balanced Substring I – LeetCode 3713 Explained

Problem in plain terms

You’re given a string s (lowercase English letters). A substring is balanced if every distinct character inside it appears the same number of times. Your task is to return the maximum length of any balanced substring.

Example idea: "abba" is balanced because a appears 2 times and b appears 2 times.

Constraints are small enough (s.length <= 1000) that we can afford an efficient “try all starts” approach.

---

The key observation

A substring is balanced when all non‑zero frequencies are equal:

• Suppose the substring has k distinct characters.
• And each appears t times.
• Then the substring length is k * t.

Now here’s the trick that makes checking fast:

If we know:

• distinct = k (how many different letters we’ve seen in the substring)
• maxCount = t (the maximum frequency of any letter in that substring)

Then the substring is balanced if and only if:

length == distinct * maxCount

Why does this work?
All character counts are ≤ maxCount. If the sum of all counts equals distinct * maxCount, then none of them can be smaller than maxCount (otherwise the sum would be smaller). So they must all be exactly maxCount.

This means we don’t need to recompute “min frequency” or compare every letter each time—just maintain distinct and maxCount as we expand the substring.

---

Approach

We’ll scan all substrings using a simple nested loop:

1. Pick a start index i
2. Expand the end index j from i to the end
3. Maintain:
   • freq[26] = frequency of each letter
   • distinct = how many letters have frequency > 0
   • maxCount = the largest frequency currently in the window
4. If (j - i + 1) == distinct * maxCount, update the answer.

Because there are only 26 lowercase letters, updates are constant time, and n is only up to 1000.

---

Walkthrough on a quick example

s = "abbac" → answer is 4, from "abba".

When we consider substring "abba":

• frequencies: a=2, b=2
• distinct = 2, maxCount = 2
• length = 4
• distinct * maxCount = 2 * 2 = 4 ✅ balanced

---

Time and space complexity

• Time: O(n^2) (about 500k substring expansions when n=1000)
• Space: O(1) (fixed 26-size frequency array)

This is well within limits.

---

Python solution (clean and fast)

class Solution:
    def longestBalanced(self, s: str) -> int:
        n = len(s)
        ans = 1  # any single character substring is balanced

        for i in range(n):
            freq = [0] * 26
            distinct = 0
            maxCount = 0

            for j in range(i, n):
                idx = ord(s[j]) - ord('a')
                if freq[idx] == 0:
                    distinct += 1
                freq[idx] += 1
                if freq[idx] > maxCount:
                    maxCount = freq[idx]

                length = j - i + 1
                if length == distinct * maxCount:
                    ans = max(ans, length)

        return ans

---

Common pitfalls

• Counting total odds/evens or using prefix sums: doesn’t apply here because the balance is across all distinct characters, not just two types.
• Forgetting that 1-character substrings are balanced: because all distinct characters (just one) occur the same number of times.