Finding patterns within a sea of characters is a fundamental skill in both competitive programming and software engineering. This problem challenges you to identify specific substrings where every unique character plays an equal role in the count.
Problem Summary
You're given:
A string containing lowercase English letters.
Your goal:
Find the length of the longest substring where every distinct character appears the exact same number of times.
Intuition
To solve this problem, we need to examine different parts of the string and count how often characters appear. Since the string length is relatively small (up to 1000 characters), we can use a nested loop approach.
The core logic revolves around two variables:
- Distinct Character Count (): How many different letters are in the current substring.
- Maximum Frequency (): The highest number of times any single letter appears in that substring.
If a substring is "balanced," then every distinct character must appear times. Mathematically, if we have distinct characters and each appears times, the total length of the substring must be exactly . If this condition holds true for our current window, we update our maximum length.
Walkthrough: Understanding the Examples
Let's look at Example 1: s = "abbac"
- We start checking substrings beginning at index 0.
- Substring "a": Distinct = 1, Max Freq = 1. . Length matches.
- Substring "ab": Distinct = 2, Max Freq = 1. . Length matches.
- Substring "abb": Distinct = 2, Max Freq = 2. . Length (3) does not match.
- Substring "abba": Distinct = 2 ('a' and 'b'), Max Freq = 2 (both appear twice). . Length (4) matches! This is our current winner.
Code Implementation
C++
class Solution {
public:
int longestBalanced(string s) {
int n = s.size();
vector<int> cnt(26, 0);
int ans = 0;
for (int i = 0; i < n; ++i) {
fill(cnt.begin(), cnt.end(), 0);
int mx = 0, v = 0;
for (int j = i; j < n; ++j) {
int c = s[j] - 'a';
if (++cnt[c] == 1) {
++v;
}
mx = max(mx, cnt[c]);
// If total length equals (distinct characters * max frequency), it is balanced
if (mx * v == j - i + 1) {
ans = max(ans, j - i + 1);
}
}
}
return ans;
}
};
Python
class Solution:
def longestBalanced(self, s: str) -> int:
n = len(s)
ans = 0
for i in range(n):
cnt = [0] * 26
mx = 0
v = 0
for j in range(i, n):
c = ord(s[j]) - ord('a')
cnt[c] += 1
if cnt[c] == 1:
v += 1
if cnt[c] > mx:
mx = cnt[c]
# Check if current window [i...j] is balanced
current_len = j - i + 1
if mx * v == current_len:
ans = max(ans, current_len)
return ans
JavaScript
/**
* @param {string} s
* @return {number}
*/
var longestBalanced = function(s) {
let n = s.length;
let ans = 0;
for (let i = 0; i < n; i++) {
let cnt = new Array(26).fill(0);
let mx = 0;
let v = 0;
for (let j = i; j < n; j++) {
let c = s.charCodeAt(j) - 97; // 'a' is 97
if (++cnt[c] === 1) {
v++;
}
mx = Math.max(mx, cnt[c]);
let currentLen = j - i + 1;
if (mx * v === currentLen) {
ans = Math.max(ans, currentLen);
}
}
}
return ans;
};
Key Takeaways
- Frequency Arrays: Using an array of size 26 is a highly efficient way to track character counts when dealing with lowercase English letters.
- Brute Force with Optimization: While we use nested loops resulting in time complexity, we optimize by updating our counts incrementally rather than re-scanning the substring.
- Mathematical Validation: Using the property allows us to verify a "balanced" state in time within our inner loop.
Final Thoughts
This problem is a fantastic exercise in "windowing" logic. In the real world, these types of balanced patterns are often used in data validation and signal processing, where you need to ensure that different categories of data are distributed evenly. For coding interviews, mastering the ability to track multiple properties (like distinct counts and max frequency) simultaneously is a key differentiator between junior and senior developers.
Top comments (0)