Longest Balanced Substring I

medium string counting enumeration

Problem

You are given a string s of lowercase English letters. A substring is balanced if every distinct character inside it appears the same number of times. Return the length of the longest balanced substring of s.

Inputs = "abbac"

Output4

The substring "abba" is balanced: both 'a' and 'b' appear exactly 2 times.

s (lowercase letters)

def longestBalanced(s):
    n = len(s)
    best = 0
    for i in range(n):                       # start of substring
        cnt = [0] * 26                       # fresh character counts
        for j in range(i, n):                # extend the substring
            cnt[ord(s[j]) - 97] += 1
            lo, hi = 1 << 30, 0              # min / max non-zero count
            for c in cnt:
                if c > 0:
                    lo = min(lo, c)
                    hi = max(hi, c)
            if lo == hi:                      # all distinct chars equal
                best = max(best, j - i + 1)
    return best

function longestBalanced(s) {
  const n = s.length;
  let best = 0;
  for (let i = 0; i < n; i++) {            // start of substring
    const cnt = new Array(26).fill(0);     // fresh character counts
    for (let j = i; j < n; j++) {          // extend the substring
      cnt[s.charCodeAt(j) - 97]++;
      let lo = Infinity, hi = 0;           // min / max non-zero count
      for (const c of cnt) {
        if (c > 0) { lo = Math.min(lo, c); hi = Math.max(hi, c); }
      }
      if (lo === hi) {                      // all distinct chars equal
        best = Math.max(best, j - i + 1);
      }
    }
  }
  return best;
}

int longestBalanced(String s) {
    int n = s.length(), best = 0;
    for (int i = 0; i < n; i++) {          // start of substring
        int[] cnt = new int[26];           // fresh character counts
        for (int j = i; j < n; j++) {      // extend the substring
            cnt[s.charAt(j) - 'a']++;
            int lo = Integer.MAX_VALUE, hi = 0;
            for (int c : cnt) {
                if (c > 0) { lo = Math.min(lo, c); hi = Math.max(hi, c); }
            }
            if (lo == hi) {                 // all distinct chars equal
                best = Math.max(best, j - i + 1);
            }
        }
    }
    return best;
}

int longestBalanced(string s) {
    int n = s.size(), best = 0;
    for (int i = 0; i < n; i++) {          // start of substring
        int cnt[26] = {0};                 // fresh character counts
        for (int j = i; j < n; j++) {      // extend the substring
            cnt[s[j] - 'a']++;
            int lo = INT_MAX, hi = 0;       // min / max non-zero count
            for (int c : cnt) {
                if (c > 0) { lo = min(lo, c); hi = max(hi, c); }
            }
            if (lo == hi) {                 // all distinct chars equal
                best = max(best, j - i + 1);
            }
        }
    }
    return best;
}

Explanation

The string is short (at most 1000 characters), so we can afford to enumerate every substring and test each one directly — this is exactly the brute-force the hint suggests.

We fix a start index i and grow the substring one character at a time by sliding the end index j forward. As j moves we keep a frequency array cnt of the 26 lowercase letters, incrementing the count of the newly added character s[j]. Resetting cnt whenever i changes lets each start build its counts from scratch.

A substring is balanced when all of its distinct characters share one common frequency. To test this we scan the non-zero entries of cnt and track their minimum lo and maximum hi. If lo == hi then every present character has the same count, so the window is balanced and its length j - i + 1 can update best.

For s = "abbac", the window starting at index 0 reaches "abba" where both 'a' and 'b' have count 2, giving a balanced length of 4. No longer balanced window exists, so the answer is 4.

There are O(n²) substrings and each balance check scans the 26-slot count array, so the whole search is O(n² · 26) — comfortably fast for the given limits.

Time: O(n² · 26) Space: O(26)