Longest Balanced Substring II - Solution & Explanation

Problem Overview: You are given a string and must find the length of the longest substring that is balanced. A substring is balanced when two categories of characters appear in equal count. The goal is to scan the string and efficiently detect the largest range where this balance condition holds.

Approach 1: Enumeration (Brute Force) (Time: O(n^2), Space: O(1))

The most direct strategy checks every possible substring. Start each substring at index i, expand to j, and maintain counters for the two character groups. Each time the counts become equal, update the maximum length. This works because every candidate substring is evaluated exactly once. The drawback is the quadratic runtime: for a string of length n, there are O(n^2) substrings to examine. This approach helps you reason about the balance condition but quickly becomes too slow for large inputs.

Approach 2: Enumeration + Prefix Sum + Hash Table (Time: O(n), Space: O(n))

The optimal method converts the balance condition into a prefix sum problem. Map one character category to +1 and the other to -1. As you iterate through the string, maintain a running prefix sum representing the difference between the two counts. When the same prefix value appears at two indices, the substring between them has equal numbers of both characters because the net difference cancels out.

Use a hash table to store the earliest index where each prefix sum occurs. When you encounter the same prefix sum again, compute the candidate length current_index - first_index. Keep the maximum across the scan. This reduces the problem to a single pass with constant-time hash lookups. The technique is a classic application of Prefix Sum combined with a Hash Table to track previously seen states. The string is processed once, giving O(n) time complexity and O(n) additional space.

This pattern appears frequently in substring problems where equality or balance constraints exist. Instead of recomputing counts for every substring, the prefix difference encodes the state of the scan, and repeated states reveal balanced ranges automatically. Similar ideas also appear in other String scanning problems involving equal frequency or net-zero conditions.

Recommended for interviews: Start by describing the brute force enumeration to demonstrate understanding of the balance definition. Then move to the prefix sum + hash table optimization. Interviewers typically expect the O(n) solution because it shows you recognize the "same prefix state implies balanced subarray" pattern and can implement it efficiently with a hash map.