Frontend School

Longest Substring with Balanced Character Counts

DSA
medium

Longest Substring with Balanced Character Counts

Medium
Sliding Window
Hash Map
String

Overview

In many data processing and text analysis applications, maintaining a consistent or "balanced" distribution of elements within a segment is crucial. For instance, ensuring that no single character dominates a text snippet too heavily compared to others can be important for cryptographic analysis, data compression, or even user interface design where visual balance is desired. This problem challenges you to identify the longest segment within a given string that adheres to a specific character count balance criterion.

What you need to do / Task

Your task is to implement a function longestBalancedSubstring that takes a string s and an integer k as input. The function should return the length of the longest substring t of s such that for any two distinct characters c1 and c2 that appear in t, the absolute difference between their frequencies count(c1) and count(c2) within t is at most k. If no such substring exists (e.g., a string with only one character, where the condition is trivially met), the maximum length should still be calculated.

Specifically:

  1. Implement the longestBalancedSubstring function.
  2. The function should correctly identify and return the length of the longest substring meeting the "balanced" criteria.
  3. Handle edge cases such as k=0 or k being very large.

Input & output

  • Input:
    • s: A string consisting only of uppercase English letters ('A' through 'Z').
    • k: An integer representing the maximum allowed difference between character counts.
  • Output:
    • An integer, the length of the longest balanced substring.

Clarifications

  • A substring with only one unique character (e.g., "AAA") is always considered balanced, as there are no two distinct characters to compare. The condition |count(c1) - count(c2)| <= k trivially holds for such substrings.
  • k can be 0. If k=0, all distinct characters in the substring must have identical counts.
  • The string s will only contain uppercase English letters.

Examples

1

Example 1

Input:

s = "AABBC", k = 1

Output:

5

Note:

The entire string "AABBC" has character counts {A:2, B:2, C:1}. The minimum frequency among present characters is 1 (for 'C'), and the maximum is 2 (for 'A' and 'B'). The difference is max_freq - min_freq = 2 - 1 = 1. Since 1 <= k (1), the entire string is balanced. Its length is 5.

2

Example 2

Input:

s = "ABACABA", k = 0

Output:

3

Note:

If k=0, all distinct characters in a balanced substring must have identical counts.

  • "A", "B", "C" are balanced (length 1).
  • "AB": {A:1, B:1}. max_freq=1, min_freq=1. 1-1=0 <= 0. Balanced. Length 2.
  • "BAC": {B:1, A:1, C:1}. max_freq=1, min_freq=1. 1-1=0 <= 0. Balanced. Length 3.
  • "ABA": {A:2, B:1}. max_freq=2, min_freq=1. 2-1=1 > 0. Not balanced.
  • The longest balanced substring found is "BAC" (or "ACB", etc.) with length 3.
3

Example 3

Input:

s = "XYZXYZ", k = 100

Output:

6

Note:

The entire string "XYZXYZ" has counts {X:2, Y:2, Z:2}. max_freq = 2, min_freq = 2. The difference max_freq - min_freq = 0. Since 0 <= k (100), the entire string is balanced. Its length is 6.

Constraints

Constraints & assumptions

  • 1 <= s.length <= 10^5
  • 0 <= k <= s.length
  • s consists only of uppercase English letters ('A'-'Z').

What interviewers evaluate

  • Correctness: The solution accurately identifies the longest balanced substring for all test cases, including edge cases.
  • Algorithm Design: Demonstrates a clear understanding and correct application of the sliding window technique.
  • Time Complexity: Achieves an optimal or near-optimal time complexity, typically O(N * alphabet_size) where alphabet_size is 26.
  • Code Quality: Writes clean, readable, and well-structured code, with appropriate variable names and comments where necessary.

Loading editor...