3713. Longest Balanced Substring I

String
Hash Table
Brute Force

TIME

O(n²)

SPACE

O(1)

Intuition

A balanced substring has all distinct characters appearing the same number of times. If we have d distinct characters each appearing f times, the length is d * f. So we check if distinct * maxFreq == length.

Solution

Enumerate all substrings: For each starting index i, expand j from i to n-1.
Track frequencies: Maintain frequency array for 26 lowercase letters.
Track distinct count and max frequency:
- distinct = number of characters with freq > 0
- maxFreq = highest frequency among all characters
Check balance condition: If distinct * maxFreq == length, all characters appear exactly maxFreq times (balanced).

Why This Works

If substring length = distinct * maxFreq, it means:

We have exactly distinct unique characters
Total characters = distinct * maxFreq
This is only possible if each distinct character appears exactly maxFreq times

Complexity

Time: O(n²), enumerate all substrings
Space: O(1), fixed size frequency array (26 chars)

Edge Cases

Single character → return 1 (trivially balanced)
All same character → entire string is balanced
All distinct characters → any substring is balanced

Code

class Solution:
    def longestBalanced(self, s: str) -> int:
        """
        3713. Longest Balanced Substring I
        Time: O(n²)
        Space: O(1)
        """
        n = len(s)
        ans = 0

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

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

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

        return ans

/**
 * 3713. Longest Balanced Substring I
 * Time: O(n²)
 * Space: O(1)
 */
class Solution {
    public int longestBalancedSubstring(String s) {
        int n = s.length();
        int ans = 0;

        for (int i = 0; i < n; i++) {
            int[] freq = new int[26];
            int distinct = 0;
            int maxFreq = 0;

            for (int j = i; j < n; j++) {
                int idx = s.charAt(j) - 'a';
                if (freq[idx] == 0) {
                    distinct++;
                }
                freq[idx]++;
                maxFreq = Math.max(maxFreq, freq[idx]);

                int len = j - i + 1;
                if (distinct * maxFreq == len) {
                    ans = Math.max(ans, len);
                }
            }
        }

        return ans;
    }
}