Skip to main content
Talentd

Longest Balanced Substring I - Solution & Explanation

MediumHash TableStringCountingEnumeration10 min readAsked at: Amazon, Meta, Google +1
Practice this problem

Problem Statement

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 <= 1000
  • s consists of lowercase English letters.

Approach Overview

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.

Solution

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor ā†’

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 TableO(n^2)O(Ī£)General solution for strings up to typical interview constraints
Enumeration with Fixed Alphabet ArrayO(n^2)O(1)When the alphabet is known (e.g., lowercase letters) and you want faster constant factors

Video Solution

Longest Balanced Substring I | Easy Explanation | Leetcode 3713 | codestorywithMIK ā€¢ codestorywithMIK ā€¢ 12,805 views views

Watch 9 more video solutions ā†’

Frequently Asked Questions

Is Longest Balanced Substring I easy or hard?
Longest Balanced Substring I is usually classified as a Medium problem. The logic is straightforward once you recognize that substring enumeration combined with frequency counting can validate the balanced condition efficiently.
Longest Balanced Substring I Python/Java solution
Python and Java implementations typically use a dictionary or HashMap to track character frequencies while expanding the substring. Each iteration updates the count of the current character and checks whether all stored frequencies match the expected balanced value.
How to solve Longest Balanced Substring I in O(n)?
A strict O(n) solution is generally not feasible because balanced validation depends on the frequency distribution of multiple characters within arbitrary substrings. Most implementations rely on enumerating start indices and maintaining counts, resulting in O(n^2) time while keeping updates constant with a hash table.
What is the best approach for Longest Balanced Substring I?
The standard solution uses enumeration with frequency counting. For each starting index, expand the substring and maintain a hash table of character counts. A substring is balanced when every character appears the same number of times. This approach runs in O(n^2) time and O(Ī£) space, where Ī£ is the alphabet size.
Is Longest Balanced Substring I asked at Google/Amazon/Meta?
Substring frequency and balance problems frequently appear in interviews at companies like Amazon, Google, and Meta. While the exact problem title may vary, the pattern of enumerating substrings and maintaining character counts with hash tables is a common interview topic.
What data structure is used in Longest Balanced Substring I?
The core data structure is a hash table (or fixed-size frequency array) used to store character counts while expanding the substring. This allows constant-time updates and quick verification of whether all characters appear equally.
What is the time complexity of Longest Balanced Substring I?
The common optimized solution runs in O(n^2) time. You enumerate each starting index and expand the substring while updating character frequencies incrementally. Space complexity is O(Ī£), typically constant when the alphabet size is limited (like 26 lowercase letters).

Ready to solve this problem?

Practice Longest Balanced Substring I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Longest Substring Without Repeating Characters