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.
We can enumerate the starting position i of substrings in the range [0,..n-1], then enumerate the ending position j of substrings in the range [i,..,n-1], and use a hash table cnt to record the frequency of each character in substring s[i..j]. We use variable mx to record the maximum frequency of characters in the substring, and use variable v to record the number of distinct characters in the substring. If at some position j, we have mx times v = j - i + 1, it means substring s[i..j] is a balanced substring, and we update the answer ans = max(ans, j - i + 1).
The time complexity is O(n^2), where n is the length of the string. The space complexity is O(|\Sigma|), where |\Sigma| is the size of the character set, which is |\Sigma| = 26 in this problem.
| 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 |
Longest Balanced Substring I | Easy Explanation | Leetcode 3713 | codestorywithMIK • codestorywithMIK • 11,396 views views
Watch 9 more video solutions →Practice Longest Balanced Substring I with our built-in code editor and test cases.
Practice on FleetCode