Watch 10 video solutions for Longest Balanced Substring I, a medium level problem involving Hash Table, String, Counting. This walkthrough by codestorywithMIK has 11,396 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a string s consisting of lowercase English letters.
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 = "zzabccy"
Output: 4
Explanation:
The longest balanced substring is "zabc" because the distinct characters 'z', '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 <= 1000s consists of lowercase English letters.Problem Overview: You are given a string and need the length of the longest substring where all characters that appear in the substring occur the same number of times. The substring can contain any set of characters, but their frequencies must be equal.
Approach 1: Enumeration + Counting (O(n2) time, O(Σ) space)
Enumerate every possible substring start index and extend the end index step by step. Maintain a frequency map using a hash table while expanding the substring. For each extension, update the count of the current character and track how many distinct characters exist in the window.
A substring is balanced when all character frequencies are equal. If the substring length is len and it contains k distinct characters, then each character must appear exactly len / k times. After updating the frequency map, verify this condition by checking whether every stored count matches the expected frequency. When it does, update the maximum length.
This approach works well because counting updates happen in constant time using a hash table. Enumeration guarantees every candidate substring is considered, while frequency tracking ensures you can quickly test whether the substring satisfies the balanced constraint. Since each starting position expands across the string, the overall runtime becomes O(n2).
The space usage stays small because the frequency structure only stores characters present in the current substring. In practice, the size is bounded by the alphabet size (for example 26 for lowercase letters), so the auxiliary space is effectively constant.
Recommended for interviews: The enumeration + counting strategy is typically what interviewers expect. It demonstrates understanding of substring enumeration and efficient frequency tracking with a hash table and string traversal. Brute force without incremental counting would recompute frequencies repeatedly, which is inefficient. Maintaining counts while expanding the window shows better algorithmic thinking and keeps the solution within O(n2) time.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force (recount every substring) | O(n^3) | O(Σ) | Useful only for understanding the problem or very small inputs |
| Enumeration + Counting with Hash Table | O(n^2) | O(Σ) | General solution for strings up to typical interview constraints |
| Enumeration with Fixed Alphabet Array | O(n^2) | O(1) | When the alphabet is known (e.g., lowercase letters) and you want faster constant factors |