3714. Longest Balanced Substring II

/**
 * Problem: LeetCode 3714 - Longest Balanced Substring II
 * Difficulty: Medium
 * Language: Java
 * Author: CodeByTushu
 */
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int longestBalanced(String s) {
        int n = s.length();
        int maxLen = 1;

        // Case 1: Substring contains exactly 1 distinct character
        // The longest balanced substring is the longest consecutive run of identical characters.
        int curRun = 1;
        for (int i = 1; i < n; i++) {
            if (s.charAt(i) == s.charAt(i - 1)) {
                curRun++;
            } else {
                curRun = 1;
            }
            if (curRun > maxLen) {
                maxLen = curRun;
            }
        }

        // Case 2: Substring contains exactly 2 distinct characters
        // Pairs: (a, b) avoiding c, (b, c) avoiding a, (a, c) avoiding b
        char[][] pairs = {
            {'a', 'b', 'c'},
            {'b', 'c', 'a'},
            {'a', 'c', 'b'}
        };

        for (char[] p : pairs) {
            char c1 = p[0], c2 = p[1], avoid = p[2];
            int start = 0;
            while (start < n) {
                while (start < n && s.charAt(start) == avoid) {
                    start++;
                }
                if (start >= n) {
                    break;
                }
                int end = start;
                while (end < n && s.charAt(end) != avoid) {
                    end++;
                }

                Map<Integer, Integer> map = new HashMap<>();
                map.put(0, start - 1);
                int diff = 0;
                for (int i = start; i < end; i++) {
                    char ch = s.charAt(i);
                    if (ch == c1) {
                        diff++;
                    } else if (ch == c2) {
                        diff--;
                    }

                    if (map.containsKey(diff)) {
                        int len = i - map.get(diff);
                        if (len > maxLen) {
                            maxLen = len;
                        }
                    } else {
                        map.put(diff, i);
                    }
                }
                start = end;
            }
        }

        // Case 3: Substring contains all 3 distinct characters
        // Equal frequencies: cnt[a] - cnt[b] == 0 and cnt[b] - cnt[c] == 0 relative to prefix.
        Map<Long, Integer> stateMap = new HashMap<>();
        stateMap.put(encode(0, 0), -1);
        int ca = 0, cb = 0, cc = 0;

        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if (ch == 'a') {
                ca++;
            } else if (ch == 'b') {
                cb++;
            } else if (ch == 'c') {
                cc++;
            }

            long key = encode(ca - cb, cb - cc);
            if (stateMap.containsKey(key)) {
                int len = i - stateMap.get(key);
                if (len > maxLen) {
                    maxLen = len;
                }
            } else {
                stateMap.put(key, i);
            }
        }

        return maxLen;
    }

    private long encode(int d1, int d2) {
        return (((long) d1) << 32) | (d2 & 0xFFFFFFFFL);
    }
}

"""
Problem: LeetCode 3714 - Longest Balanced Substring II
Difficulty: Medium
Language: Python
Author: CodeByTushu
"""
class Solution:
    def longestBalanced(self, s: str) -> int:
        n = len(s)
        max_len = 1

        # Case 1: Exactly 1 distinct character
        cur_run = 1
        for i in range(1, n):
            if s[i] == s[i - 1]:
                cur_run += 1
            else:
                cur_run = 1
            if cur_run > max_len:
                max_len = cur_run

        # Case 2: Exactly 2 distinct characters
        pairs = [
            ('a', 'b', 'c'),
            ('b', 'c', 'a'),
            ('a', 'c', 'b')
        ]

        for c1, c2, avoid in pairs:
            start = 0
            while start < n:
                while start < n and s[start] == avoid:
                    start += 1
                if start >= n:
                    break
                end = start
                while end < n and s[end] != avoid:
                    end += 1

                pos_map = {0: start - 1}
                diff = 0
                for i in range(start, end):
                    if s[i] == c1:
                        diff += 1
                    elif s[i] == c2:
                        diff -= 1

                    if diff in pos_map:
                        length = i - pos_map[diff]
                        if length > max_len:
                            max_len = length
                    else:
                        pos_map[diff] = i
                start = end

        # Case 3: Exactly 3 distinct characters
        state_map = {(0, 0): -1}
        ca = cb = cc = 0
        for i in range(n):
            if s[i] == 'a':
                ca += 1
            elif s[i] == 'b':
                cb += 1
            elif s[i] == 'c':
                cc += 1

            state = (ca - cb, cb - cc)
            if state in state_map:
                length = i - state_map[state]
                if length > max_len:
                    max_len = length
            else:
                state_map[state] = i

        return max_len

/**
 * Problem: LeetCode 3714 - Longest Balanced Substring II
 * Difficulty: Medium
 * Language: C++
 * Author: CodeByTushu
 */
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

class Solution {
public:
    int longestBalanced(string s) {
        int n = s.length();
        int maxLen = 1;

        // Case 1: Exactly 1 distinct character
        int curRun = 1;
        for (int i = 1; i < n; i++) {
            if (s[i] == s[i - 1]) {
                curRun++;
            } else {
                curRun = 1;
            }
            if (curRun > maxLen) {
                maxLen = curRun;
            }
        }

        // Case 2: Exactly 2 distinct characters
        vector<vector<char>> pairs = {
            {'a', 'b', 'c'},
            {'b', 'c', 'a'},
            {'a', 'c', 'b'}
        };

        for (const auto& p : pairs) {
            char c1 = p[0], c2 = p[1], avoid = p[2];
            int start = 0;
            while (start < n) {
                while (start < n && s[start] == avoid) {
                    start++;
                }
                if (start >= n) {
                    break;
                }
                int end = start;
                while (end < n && s[end] != avoid) {
                    end++;
                }

                unordered_map<int, int> map;
                map[0] = start - 1;
                int diff = 0;
                for (int i = start; i < end; i++) {
                    if (s[i] == c1) {
                        diff++;
                    } else if (s[i] == c2) {
                        diff--;
                    }

                    auto it = map.find(diff);
                    if (it != map.end()) {
                        int len = i - it->second;
                        if (len > maxLen) {
                            maxLen = len;
                        }
                    } else {
                        map[diff] = i;
                    }
                }
                start = end;
            }
        }

        // Case 3: Exactly 3 distinct characters
        unordered_map<long long, int> stateMap;
        stateMap[encode(0, 0)] = -1;
        int ca = 0, cb = 0, cc = 0;

        for (int i = 0; i < n; i++) {
            if (s[i] == 'a') {
                ca++;
            } else if (s[i] == 'b') {
                cb++;
            } else if (s[i] == 'c') {
                cc++;
            }

            long long key = encode(ca - cb, cb - cc);
            auto it = stateMap.find(key);
            if (it != stateMap.end()) {
                int len = i - it->second;
                if (len > maxLen) {
                    maxLen = len;
                }
            } else {
                stateMap[key] = i;
            }
        }

        return maxLen;
    }

private:
    long long encode(int d1, int d2) {
        return (((long long)d1) << 32) | ((unsigned int)d2);
    }
};

/**
 * Problem: LeetCode 3714 - Longest Balanced Substring II
 * Difficulty: Medium
 * Language: JavaScript
 * Author: CodeByTushu
 */
/**
 * @param {string} s
 * @return {number}
 */
var longestBalanced = function(s) {
    const n = s.length;
    let maxLen = 1;

    // Case 1: Exactly 1 distinct character
    let curRun = 1;
    for (let i = 1; i < n; i++) {
        if (s[i] === s[i - 1]) {
            curRun++;
        } else {
            curRun = 1;
        }
        if (curRun > maxLen) {
            maxLen = curRun;
        }
    }

    // Case 2: Exactly 2 distinct characters
    const pairs = [
        ['a', 'b', 'c'],
        ['b', 'c', 'a'],
        ['a', 'c', 'b']
    ];

    for (const [c1, c2, avoid] of pairs) {
        let start = 0;
        while (start < n) {
            while (start < n && s[start] === avoid) {
                start++;
            }
            if (start >= n) {
                break;
            }
            let end = start;
            while (end < n && s[end] !== avoid) {
                end++;
            }

            const map = new Map();
            map.set(0, start - 1);
            let diff = 0;
            for (let i = start; i < end; i++) {
                if (s[i] === c1) {
                    diff++;
                } else if (s[i] === c2) {
                    diff--;
                }

                if (map.has(diff)) {
                    const len = i - map.get(diff);
                    if (len > maxLen) {
                        maxLen = len;
                    }
                } else {
                    map.set(diff, i);
                }
            }
            start = end;
        }
    }

    // Case 3: Exactly 3 distinct characters
    const stateMap = new Map();
    stateMap.set('0,0', -1);
    let ca = 0, cb = 0, cc = 0;

    for (let i = 0; i < n; i++) {
        if (s[i] === 'a') {
            ca++;
        } else if (s[i] === 'b') {
            cb++;
        } else if (s[i] === 'c') {
            cc++;
        }

        const key = `${ca - cb},${cb - cc}`;
        if (stateMap.has(key)) {
            const len = i - stateMap.get(key);
            if (len > maxLen) {
                maxLen = len;
            }
        } else {
            stateMap.set(key, i);
        }
    }

    return maxLen;
};