M3900.一次交换后的最长平衡子串

https://leetcode.cn/problems/longest-balanced-substring-after-one-swap/

【黄宇曦 地球与空间科学学院】第一反应是滑动窗口，结果发现过不去，这不毁了？！

转念一想去思考前缀和 / 哈希。我们去思考合法的 $l$ 要满足什么样的性质。首先区间内 $\mathrm{\#}1=\mathrm{\#}0$ 肯定满足要求。我们去思考 $\mathrm{\#}0-\mathrm{\#}1=2$ 的情况。这要求区间外的 $\mathrm{\#}0\ge 1$。那么考虑 $[l,r]$ 这个范围内的数，必然有 $\mathrm{\#}0=\frac{r-l}{2}+1$。于是 $$#0_{\text{out}}\geq 1\implies S_0-# 0\geq 1\implies 2S_0-r+l+2\geq 1\implies l\gt r-2-2S_0.$$另外一边完全同理。所以写两个二分查找就解决了。时间复杂度 $O(n\log n)$。

class Solution {
public:
    int longestBalanced(string str) {
        unordered_map<int, vector<int>> mp;
        int s = 0, ans = 0, cnt[2]{};
        for (int i = 0; i < str.size(); i++) {
            cnt[0] += str[i] == '0';
            cnt[1] += str[i] == '1';
        }
        mp[0].push_back(-1);
        for (int i = 0; i < str.size(); i++) {
            s += str[i] == '1' ? 1 : -1;
            if (mp.count(s)) {
                ans = max(ans, i - mp[s].front());
            }
            if (mp.count(s - 2)) {
                auto it = upper_bound(mp[s - 2].begin(), mp[s - 2].end(),
                                      i - 2 - 2 * cnt[0]);
                if (it != mp[s - 2].end()) {
                    ans = max(ans, i - *it);
                }
            }
            if (mp.count(s + 2)) {
                auto it = upper_bound(mp[s + 2].begin(), mp[s + 2].end(),
                                      i - 2 - 2 * cnt[1]);
                if (it != mp[s + 2].end()) {
                    ans = max(ans, i - *it);
                }
            }
            mp[s].push_back(i);
        }
        return ans;
    }
};