Source: Dev.to

Longest Balanced Substring

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.

---

Problem Statement

You are given a string s consisting only of the characters 'a', 'b', and 'c'.
Your goal is to determine the length of the longest substring that is balanced, i.e., each distinct character in the substring occurs the same number of times.

A substring is considered balanced in three possible ways:

1. Single‑character substring – any sequence of the same character (e.g., "aaaa").
2. Two‑character substring – a substring containing exactly two different characters with equal counts (e.g., "aabb").
3. Three‑character substring – a substring containing 'a', 'b', and 'c' where the three counts are identical (e.g., "abc").

---

Approach

The solution uses prefix sums together with hash maps to track the relative differences between character counts while scanning the string once.

1. One distinct character

Simply find the longest run of identical characters.

2. Two distinct characters

For each pair ('a','b'), ('b','c'), ('a','c'):

• Keep a running difference diff = (#char1) – (#char2).
• Store the earliest index where each diff value occurs in a hash map.
• When the same diff reappears at index i, the substring between the two indices has equal numbers of the two characters.
• If a third character appears, reset the map and diff.

3. Three distinct characters

Track two independent differences:

• d1 = count('a') – count('b')
• d2 = count('a') – count('c')

Store the first occurrence of each pair (d1, d2) in a map.
When the same pair reappears, the substring between the two positions has equal counts of 'a', 'b', and 'c'.

All three cases are processed in O(n) time and O(n) extra space.

---

Examples

Example 1

s = "abbac"

• Single‑character longest run: "bb" → length 2.
• Pair ('a','b') gives the substring "abba" (indices 0‑3) with two 'a' and two 'b' → length 4.

Output: 4

Example 2

s = "aabcc"

The substring "abc" contains one 'a', one 'b', and one 'c'.

Output: 3

---

Reference Implementations

C++

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

class Solution {
public:
    int longestBalanced(string s) {
        int ans = 0;
        int n = s.length();
        if (n == 0) return 0;

        /* ---------- Case 1: 1 distinct character ---------- */
        int count = 1;
        ans = 1;
        for (int i = 1; i > combos = {{'a', 'b'}, {'b', 'c'}, {'a', 'c'}};
        for (auto &p : combos) {
            char c1 = p.first, c2 = p.second;
            int diff = 0;
            unordered_map first;   // diff -> earliest index
            first[0] = -1;

            for (int i = 0; i , int> three;
        three[{0, 0}] = -1;
        int a = 0, b = 0, c = 0;

        for (int i = 0; i  key = {a - b, a - c};
            if (three.count(key))
                ans = max(ans, i - three[key]);
            else
                three[key] = i;
        }

        return ans;
    }
};

---

Python

class Solution:
    def longestBalanced(self, s: str) -> int:
        n = len(s)
        if n == 0:
            return 0

        ans = 1

        # ---------- Case 1: 1 distinct character ----------
        cnt = 1
        for i in range(1, n):
            if s[i] == s[i - 1]:
                cnt += 1
            else:
                cnt = 1
            ans = max(ans, cnt)

        # ---------- Case 2: 2 distinct characters ----------
        for c1, c2 in [('a', 'b'), ('b', 'c'), ('a', 'c')]:
            diff = 0
            first = {0: -1}          # diff -> earliest index
            for i, ch in enumerate(s):
                if ch == c1:
                    diff += 1
                elif ch == c2:
                    diff -= 1
                else:               # third character
                    first = {0: i}
                    diff = 0
                    continue

                if diff in first:
                    ans = max(ans, i - first[diff])
                else:
                    first[diff] = i

        # ---------- Case 3: 3 distinct characters ----------
        three = {(0, 0): -1}
        a = b = c = 0
        for i, ch in enumerate(s):
            if ch == 'a':
                a += 1
            elif ch == 'b':
                b += 1
            elif ch == 'c':
                c += 1

            key = (a - b, a - c)
            if key in three:
                ans = max(ans, i - three[key])
            else:
                three[key] = i

        return ans

---

JavaScript

/**
 * @param {string} s
 * @return {number}
 */
var longestBalanced = function (s) {
    const n = s.length;
    if (n === 0) return 0;

    let ans = 1;

    // ---------- Case 1: 1 distinct character ----------
    let cnt = 1;
    for (let i = 1; i  earliest index
        first.set(0, -1);

        for (let i = 0; i < n; ++i) {
            if (s[i] === c1) ++diff;
            else if (s[i] === c2) --diff;
            else {                  // third character appears
                first.clear();
                first.set(0, i);
                diff = 0;
                continue;
            }

            if (first.has(diff)) {
                ans = Math.max(ans, i - first.get(diff));
            } else {
                first.set(diff, i);
            }
        }
    }

    // ---------- Case 3: 3 distinct characters ----------
    const three = new Map();          // key = "d1,d2"
    three.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;

        const key = `${a - b},${a - c}`;
        if (three.has(key)) {
            ans = Math.max(ans, i - three.get(key));
        } else {
            three.set(key, i);
        }
    }

    return ans;
};

---

The three implementations follow the same O(n) time / O(n) space strategy and can be used as a reference for solving the problem in any of the supported languages.

// Case 2: 2 distinct characters
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 Techniques

• Prefix Sum Differences – 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 O(n) time complexity, as we only need to pass through the string a few times rather than using a nested‑loop approach which would be O(n²).

---

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.