Finding patterns in a sea of characters is a fundamental skill in software engineering. This problem challenges us to find the longest stretch of text where every unique character appears exactly the same number of times, a task that requires both precision and efficient data tracking.
Problem Summary
You're given:
A string containing only the characters 'a', 'b', and 'c'.
Your goal:
Find the length of the longest substring where every distinct character present in that substring occurs with the same frequency.
Intuition
To solve this efficiently, we need to consider three different scenarios for a "balanced" substring:
- Single Character: Any sequence of the same character (like "aaaa") is technically balanced because the only distinct character ('a') appears an equal number of times.
- Two Distinct Characters: A substring with exactly two types of characters (e.g., "aabb") where the count of the first equals the count of the second.
- Three Distinct Characters: A substring containing 'a', 'b', and 'c' where the counts of all three are identical.
The solution uses a Prefix Sum and Hash Map technique. By tracking the difference between character counts as we iterate through the string, we can identify when those counts were previously equal. If the difference between the count of 'a' and 'b' is the same at index as it was at index , then the substring between them has an equal number of 'a's and 'b's.
Walkthrough: Understanding the Examples
Example 1: s = "abbac"
- We check single characters: "bb" gives a length of 2.
- We check pairs (a and b):
- At index 0: count(a)=1, count(b)=0. Diff = 1.
- At index 3: count(a)=2, count(b)=2. Diff = 0.
Wait, the logic tracks the relative difference. The substring "abba" from index 0 to 3 has two 'a's and two 'b's. Length = 4.
Output: 4
Example 2: s = "aabcc"
- The substring "abc" has one 'a', one 'b', and one 'c'.
- Since all three distinct characters appear once, it is balanced.
- Output: 3
Implementation
C++ Solution
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <map>
#include <algorithm>
using namespace std;
class Solution {
public:
int longestBalanced(string s) {
int ans = 0;
int n = s.length();
if (n == 0) return 0;
// Case 1: Longest substring with 1 distinct character
int count = 1;
ans = 1;
for(int i = 1; i < n; i++) {
if(s[i] == s[i-1]) count++;
else count = 1;
ans = max(ans, count);
}
// Case 2: Longest substring with 2 distinct characters
vector<pair<char, char>> combinations = {{'a', 'b'}, {'b', 'c'}, {'a', 'c'}};
for(auto& p : combinations) {
char char1 = p.first;
char char2 = p.second;
int diff = 0;
unordered_map<int, int> first_occurrence;
first_occurrence[0] = -1;
for(int i = 0; i < n; i++) {
if(s[i] == char1) diff++;
else if(s[i] == char2) diff--;
else {
// If a third character appears, reset the tracking
first_occurrence.clear();
first_occurrence[0] = i;
diff = 0;
continue;
}
if(first_occurrence.count(diff)) {
ans = max(ans, i - first_occurrence[diff]);
} else {
first_occurrence[diff] = i;
}
}
}
// Case 3: Longest substring with 3 distinct characters
map<pair<int, int>, int> three_char_map;
three_char_map[{0, 0}] = -1;
int countA = 0, countB = 0, countC = 0;
for(int i = 0; i < n; i++) {
if(s[i] == 'a') countA++;
else if(s[i] == 'b') countB++;
else if(s[i] == 'c') countC++;
// We track the ratios: (a - b) and (a - c)
pair<int, int> key = {countA - countB, countA - countC};
if(three_char_map.count(key)) {
ans = max(ans, i - three_char_map[key]);
} else {
three_char_map[key] = i;
}
}
return ans;
}
};
Python Solution
class Solution:
def longestBalanced(self, s: str) -> int:
n = len(s)
if n == 0: return 0
ans = 1
# Case 1: 1 distinct character
count = 1
for i in range(1, n):
if s[i] == s[i-1]:
count += 1
else:
count = 1
ans = max(ans, count)
# Case 2: 2 distinct characters
for char1, char2 in [('a', 'b'), ('b', 'c'), ('a', 'c')]:
diff = 0
first_occ = {0: -1}
for i in range(n):
if s[i] == char1:
diff += 1
elif s[i] == char2:
diff -= 1
else:
first_occ = {0: i}
diff = 0
continue
if diff in first_occ:
ans = max(ans, i - first_occ[diff])
else:
first_occ[diff] = i
# Case 3: 3 distinct characters
three_map = {(0, 0): -1}
a, b, c = 0, 0, 0
for i in range(n):
if s[i] == 'a': a += 1
elif s[i] == 'b': b += 1
elif s[i] == 'c': c += 1
key = (a - b, a - c)
if key in three_map:
ans = max(ans, i - three_map[key])
else:
three_map[key] = i
return ans
JavaScript Solution
/**
* @param {string} s
* @return {number}
*/
var longestBalanced = function(s) {
let n = s.length;
if (n === 0) return 0;
let ans = 1;
// Case 1: 1 distinct character
let count = 1;
for (let i = 1; i < n; i++) {
if (s[i] === s[i-1]) count++;
else count = 1;
ans = Math.max(ans, count);
}
// Case 2: 2 distinct characters
const pairs = [['a', 'b'], ['b', 'c'], ['a', 'c']];
for (const [char1, char2] of pairs) {
let diff = 0;
let firstOcc = new Map();
firstOcc.set(0, -1);
for (let i = 0; i < n; i++) {
if (s[i] === char1) diff++;
else if (s[i] === char2) diff--;
else {
firstOcc = new Map();
firstOcc.set(0, i);
diff = 0;
continue;
}
if (firstOcc.has(diff)) {
ans = Math.max(ans, i - firstOcc.get(diff));
} else {
firstOcc.set(diff, i);
}
}
}
// Case 3: 3 distinct characters
let threeMap = new Map();
threeMap.set("0,0", -1);
let a = 0, b = 0, c = 0;
for (let i = 0; i < n; i++) {
if (s[i] === 'a') a++;
else if (s[i] === 'b') b++;
else if (s[i] === 'c') c++;
let key = `${a - b},${a - c}`;
if (threeMap.has(key)) {
ans = Math.max(ans, i - threeMap.get(key));
} else {
threeMap.set(key, i);
}
}
return ans;
};
Key Takeaways
- Prefix Sum Differences: This is a powerful pattern for problems involving "equal counts." Instead of checking counts repeatedly, we track the difference between counts and store the first time that specific difference occurred.
- Sub-problem Decomposition: We broke the problem into three distinct cases (1, 2, or 3 characters) to handle the "all distinct characters" requirement cleanly.
- Hash Map Optimization: Using a Map allows us to achieve time complexity, as we only need to pass through the string a few times rather than using a nested loop approach which would be .
Final Thoughts
This problem is a classic example of how hash maps can turn a brute-force search into an efficient linear scan. In real-world systems, these techniques are used in data stream processing and log analysis, where you might need to find balanced periods of activity across multiple different services or signals. Mastering the "difference tracking" logic is a major step forward for any aspiring software engineer.
Top comments (0)