Watch 10 video solutions for Longest Balanced Substring II, a medium level problem involving Hash Table, String, Prefix Sum. This walkthrough by codestorywithMIK has 13,830 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a string s consisting only of the characters 'a', 'b', and 'c'.
A substring of s is called balanced if all distinct characters in the substring appear the same number of times.
Return the length of the longest balanced substring of s.
Example 1:
Input: s = "abbac"
Output: 4
Explanation:
The longest balanced substring is "abba" because both distinct characters 'a' and 'b' each appear exactly 2 times.
Example 2:
Input: s = "aabcc"
Output: 3
Explanation:
The longest balanced substring is "abc" because all distinct characters 'a', 'b' and 'c' each appear exactly 1 time.
Example 3:
Input: s = "aba"
Output: 2
Explanation:
One of the longest balanced substrings is "ab" because both distinct characters 'a' and 'b' each appear exactly 1 time. Another longest balanced substring is "ba".
Constraints:
1 <= s.length <= 105s contains only the characters 'a', 'b', and 'c'.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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Enumeration (Brute Force) | O(n^2) | O(1) | Small inputs or when first reasoning about the balance condition |
| Prefix Sum + Hash Table | O(n) | O(n) | General case and interview settings requiring optimal linear-time solution |