Description
You are given a string s consisting only of the characters 'a', 'b', and 'c'.
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 = "aabcc"
Output: 3
Explanation:
The longest balanced substring is "abc" because all distinct characters '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 <= 105scontains only the characters'a','b', and'c'.
Solutions
This code finds the longest balanced substring by testing multiple pattern-matching strategies. The oneChar function finds the longest run of identical consecutive characters. The twoChars function (called three times with pairs like 'a'+'b', 'a'+'c', 'b'+'c') identifies balanced substrings where one character increments a balance counter and the other decrements it — it uses an array indexed by balance level to remember the first position each level was seen, so when a balance repeats, it knows a balanced substring exists between those positions. The threeChars function handles all three characters simultaneously by tracking two balance dimensions (d1 = count_a - count_b and d2 = count_b - count_c) in a map; whenever the same 2D balance state is encountered again, the substring between those positions is balanced. The main function tries all five approaches and returns the maximum length found, ensuring it catches balanced substrings under any combination of character patterns.
/**
* @param {string} s
* @return {number}
*/
var longestBalanced = function (s) {
return Math.max(
oneChar(s),
twoChars(s, 'a', 'b'),
twoChars(s, 'a', 'c'),
twoChars(s, 'b', 'c'),
threeChars(s),
);
};
const oneChar = (s) => {
const n = s.length;
let ans = 0;
for (let i = 0; i < n;) {
const start = i++;
while (i < n && s[i] === s[i - 1])
i++;
ans = Math.max(ans, i - start);
}
return ans;
};
const twoChars = (s, x, y) => {
const n = s.length;
let best = 0;
const first = new Int32Array(2 * n + 1);
first.fill(2147483647);
const touched = new Int32Array(2 * n + 1);
let touchedSz = 0;
let i = 0;
while (i < n) {
const segStart = i;
first[n] = segStart - 1;
touched[touchedSz++] = n;
let d = 0;
while (i < n && (s[i] === x || s[i] === y)) {
d += (s[i] === x) ? 1 : -1;
const idx = d + n;
if (first[idx] !== 2147483647)
best = Math.max(best, i - first[idx]);
else {
first[idx] = i;
touched[touchedSz++] = idx;
}
i++;
}
for (let k = 0; k < touchedSz; k++)
first[touched[k]] = 2147483647;
touchedSz = 0;
i++;
}
return best;
};
const key = (d1, d2) => d1 + "," + d2;
const threeChars = (s) => {
const n = s.length;
let ans = 0;
const pos = new Map();
pos.set(key(0, 0), -1);
let ca = 0, cb = 0, cc = 0;
for (let i = 0; i < n; i++) {
const ch = s[i];
if (ch === 'a')
ca++;
else if (ch === 'b')
cb++;
else if (ch === 'c')
cc++;
const d1 = ca - cb;
const d2 = cb - cc;
const k = key(d1, d2);
if (pos.has(k))
ans = Math.max(ans, i - pos.get(k));
else pos.set(k, i);
}
return ans;
};