1class Solution {
2
3    public int longestBalanced(String s) {
4        char[] chars = s.toCharArray();
5
6        // Case 1: substring consists of exactly one distinct character.
7        int oneChar = calc1(chars);
8
9        // Case 2: substring consists of exactly two distinct characters,
10        // each appearing the same number of times. Try all three pairs.
11        int twoChars = Math.max(
12                calc2(chars, 'a', 'b'),
13                Math.max(calc2(chars, 'b', 'c'), calc2(chars, 'a', 'c'))
14        );
15
16        // Case 3: substring contains all three characters,
17        // each appearing the same number of times.
18        int threeChars = calc3(chars);
19
20        return Math.max(oneChar, Math.max(twoChars, threeChars));
21    }
22
23    /**
24     * Finds the longest run of a single repeated character.
25     * A block of identical characters is trivially balanced.
26     */
27    private int calc1(char[] s) {
28        int best = 0;
29        int i = 0;
30        int n = s.length;
31        while (i < n) {
32            // Extend j to the end of the current run of identical characters.
33            int j = i + 1;
34            while (j < n && s[j] == s[i]) {
35                j++;
36            }
37            best = Math.max(best, j - i);
38            i = j; // Jump to the start of the next run.
39        }
40        return best;
41    }
42
43    /**
44     * Finds the longest substring made up only of characters {a, b}
45     * in which a and b occur equally often.
46     *
47     * Technique: within each maximal segment containing only a/b,
48     * track the running difference d = count(a) - count(b).
49     * If the same difference appears at two indices, the substring
50     * between them is balanced.
51     */
52    private int calc2(char[] s, char a, char b) {
53        int best = 0;
54        int i = 0;
55        int n = s.length;
56        while (i < n) {
57            // Skip characters that are neither a nor b.
58            while (i < n && s[i] != a && s[i] != b) {
59                i++;
60            }
61
62            // firstIndexOfDiff maps a running difference to the earliest
63            // index at which it was seen within the current segment.
64            Map<Integer, Integer> firstIndexOfDiff = new HashMap<>();
65            firstIndexOfDiff.put(0, i - 1); // Difference 0 before the segment starts.
66
67            int diff = 0;
68            // Process the maximal segment consisting only of a/b.
69            while (i < n && (s[i] == a || s[i] == b)) {
70                diff += (s[i] == a) ? 1 : -1;
71
72                Integer earliest = firstIndexOfDiff.get(diff);
73                if (earliest != null) {
74                    // Equal difference at two positions => balanced in between.
75                    best = Math.max(best, i - earliest);
76                } else {
77                    firstIndexOfDiff.put(diff, i);
78                }
79                i++;
80            }
81        }
82        return best;
83    }
84
85    /**
86     * Finds the longest substring in which 'a', 'b' and 'c'
87     * all occur the same number of times.
88     *
89     * Technique: track the pair of running differences
90     * (count(a) - count(b), count(b) - count(c)).
91     * If the same pair reappears, the substring between the two
92     * positions has equal counts of all three characters.
93     */
94    private int calc3(char[] s) {
95        // firstIndexOfKey maps an encoded difference pair to the earliest
96        // index at which it occurred.
97        Map<Long, Integer> firstIndexOfKey = new HashMap<>();
98        firstIndexOfKey.put(f(0, 0), -1); // Both differences are 0 before the string starts.
99
100        int[] count = new int[3]; // Running counts of 'a', 'b', 'c'.
101        int best = 0;
102
103        for (int i = 0; i < s.length; i++) {
104            count[s[i] - 'a']++;
105
106            int diffAB = count[0] - count[1];
107            int diffBC = count[1] - count[2];
108            long key = f(diffAB, diffBC);
109
110            Integer earliest = firstIndexOfKey.get(key);
111            if (earliest != null) {
112                // Same difference pair seen before => balanced substring in between.
113                best = Math.max(best, i - earliest);
114            } else {
115                firstIndexOfKey.put(key, i);
116            }
117        }
118        return best;
119    }
120
121    /**
122     * Encodes a pair of (possibly negative) differences into a single long key.
123     * Offsetting by 100000 makes both values non-negative; casting to long
124     * before shifting prevents int overflow.
125     */
126    private long f(int x, int y) {
127        return ((long) (x + 100000) << 20) | (y + 100000);
128    }
129}
130

1class Solution {
2public:
3    int longestBalanced(string s) {
4        // Case 1: substrings containing exactly one distinct character.
5        int best1 = calc1(s);
6
7        // Case 2: substrings containing exactly two distinct characters,
8        // checked for every unordered pair among 'a', 'b', 'c'.
9        int best2 = max({calc2(s, 'a', 'b'), calc2(s, 'b', 'c'), calc2(s, 'a', 'c')});
10
11        // Case 3: substrings containing all three characters with equal counts.
12        int best3 = calc3(s);
13
14        return max({best1, best2, best3});
15    }
16
17private:
18    // Longest run consisting of a single repeated character.
19    int calc1(const string& s) {
20        int res = 0;
21        int i = 0, n = s.size();
22        while (i < n) {
23            // Extend j to the end of the current run of identical characters.
24            int j = i + 1;
25            while (j < n && s[j] == s[i]) {
26                ++j;
27            }
28            res = max(res, j - i);
29            i = j;
30        }
31        return res;
32    }
33
34    // Longest substring made up only of characters a and b
35    // in which both characters appear the same number of times.
36    int calc2(const string& s, char a, char b) {
37        int res = 0;
38        int i = 0, n = s.size();
39        while (i < n) {
40            // Skip characters that are neither a nor b;
41            // they break any candidate substring.
42            while (i < n && s[i] != a && s[i] != b) {
43                ++i;
44            }
45
46            // Map from prefix difference (count(a) - count(b))
47            // to the earliest index where that difference occurred.
48            unordered_map<int, int> firstPos;
49            firstPos[0] = i - 1;
50
51            int diff = 0;
52            // Process the maximal segment containing only a and b.
53            while (i < n && (s[i] == a || s[i] == b)) {
54                diff += (s[i] == a) ? 1 : -1;
55                auto it = firstPos.find(diff);
56                if (it != firstPos.end()) {
57                    // Same difference seen before: the substring in between
58                    // has equal counts of a and b.
59                    res = max(res, i - it->second);
60                } else {
61                    firstPos[diff] = i;
62                }
63                ++i;
64            }
65        }
66        return res;
67    }
68
69    // Encode the pair (x, y) into a single 64-bit key.
70    // Offsets keep both values non-negative before packing.
71    static long long f(int x, int y) {
72        return ((long long) (x + 100000) << 20) | (long long) (y + 100000);
73    }
74
75    // Longest substring in which 'a', 'b', and 'c' all occur
76    // the same number of times.
77    int calc3(const string& s) {
78        // Map from the encoded difference pair to the earliest prefix index.
79        unordered_map<long long, int> firstPos;
80        firstPos[f(0, 0)] = -1;
81
82        int cnt[3] = {0, 0, 0};
83        int res = 0;
84
85        for (int i = 0; i < (int) s.size(); ++i) {
86            char c = s[i];
87            ++cnt[c - 'a'];
88
89            // Two independent differences fully describe the balance state:
90            // equal differences imply equal counts of all three characters
91            // within the enclosed substring.
92            int x = cnt[0] - cnt[1];
93            int y = cnt[1] - cnt[2];
94            long long key = f(x, y);
95
96            auto it = firstPos.find(key);
97            if (it != firstPos.end()) {
98                // Same state seen before: the substring in between is balanced.
99                res = max(res, i - it->second);
100            } else {
101                firstPos[key] = i;
102            }
103        }
104        return res;
105    }
106};
107

1/**
2 * Returns the length of the longest balanced substring of s.
3 * A substring is balanced if every distinct character in it
4 * appears the same number of times.
5 *
6 * The answer is the maximum over three cases:
7 *   1. The substring contains exactly one distinct character.
8 *   2. The substring contains exactly two distinct characters.
9 *   3. The substring contains all three characters 'a', 'b', 'c'.
10 */
11function longestBalanced(s: string): number {
12    // Case 1: substrings made of a single repeated character
13    const singleCharBest = calc1(s);
14
15    // Case 2: substrings containing exactly two distinct characters,
16    // checked for every unordered pair among 'a', 'b', 'c'
17    const twoCharBest = Math.max(
18        calc2(s, 'a', 'b'),
19        calc2(s, 'b', 'c'),
20        calc2(s, 'a', 'c')
21    );
22
23    // Case 3: substrings containing all three characters
24    const threeCharBest = calc3(s);
25
26    return Math.max(singleCharBest, twoCharBest, threeCharBest);
27}
28
29/**
30 * Case 1: finds the longest run of identical consecutive characters.
31 * Such a run is trivially balanced because it contains one distinct
32 * character only.
33 */
34function calc1(s: string): number {
35    let best = 0;
36    const n = s.length;
37    let i = 0;
38
39    while (i < n) {
40        // Extend j to the end of the current run of equal characters
41        let j = i + 1;
42        while (j < n && s[j] === s[i]) {
43            j++;
44        }
45        // Length of the run is j - i
46        best = Math.max(best, j - i);
47        // Jump to the start of the next run
48        i = j;
49    }
50    return best;
51}
52
53/**
54 * Case 2: finds the longest substring that consists only of the two
55 * characters a and b, with equal counts of each, and that actually
56 * contains both characters.
57 *
58 * Technique: treat a as +1 and b as -1 within each maximal block
59 * composed solely of a/b. Two prefix positions with the same running
60 * sum delimit a balanced substring. The earliest index for each sum
61 * is stored in a map.
62 */
63function calc2(s: string, a: string, b: string): number {
64    let best = 0;
65    const n = s.length;
66    let i = 0;
67
68    while (i < n) {
69        // Skip characters that are neither a nor b
70        while (i < n && s[i] !== a && s[i] !== b) {
71            i++;
72        }
73
74        // Map: running difference -> earliest index where it occurred.
75        // Sum 0 corresponds to the position just before the block starts.
76        const firstIndexOfDiff = new Map<number, number>();
77        firstIndexOfDiff.set(0, i - 1);
78
79        // Running difference: count(a) - count(b)
80        let diff = 0;
81
82        // Scan the maximal block containing only a and b
83        while (i < n && (s[i] === a || s[i] === b)) {
84            diff += s[i] === a ? 1 : -1;
85
86            const prev = firstIndexOfDiff.get(diff);
87            if (prev !== undefined) {
88                // Equal diffs => the substring (prev, i] is balanced
89                best = Math.max(best, i - prev);
90            } else {
91                // Record the first occurrence of this diff value
92                firstIndexOfDiff.set(diff, i);
93            }
94            i++;
95        }
96    }
97    return best;
98}
99
100/**
101 * Case 3: finds the longest substring in which 'a', 'b' and 'c'
102 * all appear the same number of times.
103 *
104 * Technique: maintain prefix counts of each letter. Two prefixes give
105 * a balanced substring exactly when both pairwise differences
106 * (cntA - cntB, cntB - cntC) match. The earliest index of each
107 * difference pair is stored in a map keyed by an encoded string.
108 */
109function calc3(s: string): number {
110    // Map: encoded difference pair -> earliest prefix index
111    const firstIndexOfState = new Map<string, number>();
112    // The empty prefix (index -1) has both differences equal to 0
113    firstIndexOfState.set(key(0, 0), -1);
114
115    // Prefix counts of 'a', 'b', 'c'
116    const cnt = [0, 0, 0];
117    let best = 0;
118
119    for (let i = 0; i < s.length; i++) {
120        // Convert character to index 0 ('a'), 1 ('b'), or 2 ('c')
121        const c = s.charCodeAt(i) - 97;
122        cnt[c]++;
123
124        // Pairwise differences fully describe the balance state
125        const diffAB = cnt[0] - cnt[1];
126        const diffBC = cnt[1] - cnt[2];
127        const stateKey = key(diffAB, diffBC);
128
129        const prev = firstIndexOfState.get(stateKey);
130        if (prev !== undefined) {
131            // Same state => the substring (prev, i] is balanced
132            best = Math.max(best, i - prev);
133        } else {
134            // Record the first occurrence of this state
135            firstIndexOfState.set(stateKey, i);
136        }
137    }
138    return best;
139}
140
141/**
142 * Encodes a pair of integers into a single string key
143 * suitable for use in a Map.
144 */
145function key(x: number, y: number): string {
146    return x + '#' + y;
147}
148