解法：BFS & 有序集合

因为每次操作不关心字符的具体下标，所以我们只关心当前还剩几个 0 要变。

首先容易想到 BFS 的解法：设现在有 $c$ 个 0，如果操作后变成了 $c'$ 个 0，那么从节点 $c$ 向 $c'$ 连一条边。我们要求的就是从初始节点到节点 $0$ 的最短路。

但直接 BFS 的复杂度是 $\mathcal{O}(n^2)$ 的，因为我要枚举一次操作选几个 0。对于给定的 $c$，它能到达的节点之间有没有什么关联呢？

先来看个例子，假设一共有 $n = 7$ 个字符，现在还有 $c = 4$ 个 0 要变，每次要变 $k = 5$ 个下标我们能做哪些变换？

• 选 $4$ 个 0 以及 $1$ 个 1，变化后还有 $c - 4 + 1 = c - 3$ 个 0 要变。
• 选 $3$ 个 0 以及 $2$ 个 1，变化后还有 $c - 3 + 2 = c - 1$ 个 0 要变。
• 选 $2$ 个 0 以及 $3$ 个 1，变化后还有 $c - 2 + 3 = c + 1$ 个 0 要变。

可以发现，对于给定的 $c$，变化量的奇偶性总是相同的，而且变化范围（在相同奇偶性的条件下）是连续的。

可到达的节点是连续的，就能使用 leetcode 2612. 最少翻转操作数 里的套路，不熟悉的读者可以首先学习这道题。简单来说，我们可以用一个有序集合（c++ 里的 set）维护还没有到达过的节点，这样就能用 $\mathcal{O}(\log n)$ 的复杂度找出范围内还没有访问过的下一个节点，并把该节点从有序集合里移除。BFS 复杂度降为 $\mathcal{O}(n\log n)$。

参考代码（c++）

class Solution {
public:
    int minOperations(string s, int K) {
        int n = s.size();

        int dis[n + 1];
        memset(dis, -1, sizeof(dis));
        // 按奇偶性把所有节点加入有序集合
        set<int> st[2];
        for (int i = 0; i <= n; i++) st[i & 1].insert(i);

        // 计算当前字符串有几个 0，这是我们的出发节点
        int S = 0;
        for (char c : s) if (c == '0') S++;
        queue<int> q;
        q.push(S); dis[S] = 0; st[S & 1].erase(S);

        while (!q.empty()) {
            int sn = q.front(); q.pop();
            // 计算变化的范围
            // 最多选 min(K, sn) 个 0，以及最多选 min(K, n - sn) 个 1
            int l = min(K, sn);
            l = (K - l) - l;
            int r = min(K, n - sn);
            r = r - (K - r);

            // 将指定范围里还未访问过的节点取出来，然后删除
            auto &tmp = st[(sn + l) & 1];
            auto it = tmp.lower_bound(sn + l);
            while (it != tmp.end()) {
                if (*it > sn + r) break;
                q.push(*it);
                dis[*it] = dis[sn] + 1;
                tmp.erase(it++);
            }
        }

        return dis[0];
    }
};

解法：枚举 & 前缀和 & 哈希表

先考虑简单一点的问题：如果只有字母 a 和 b 怎么做？

这是一个经典的用前缀和维护的题目。假设平衡子串的下标范围是 $[l, r]$，设 $a_i$ 表示字母 a 在长度为 $i$ 的前缀里的出现次数，$b_i$ 表示字母 b 在长度为 $i$ 的前缀里的出现次数，则

$$
a_r - a_{l - 1} = b_r - b_{l - 1}
$$

移项得

$$
a_r - b_r = a_{l - 1} - b_{l - 1}
$$

因此，类似于 leetcode 974. 和可被 K 整除的子数组，我们枚举子串的右端点 $r$，并找到 $\Delta = (a_i - b_i)$ 的值与 $r$ 相同的最小下标 $l$，则以 $r$ 为右端点的平衡子串的最大长度就是 $(r - l)$。我们可以把 $\Delta$ 的值放入哈希表，并对每个 $\Delta$ 维护最小的下标。

回到当前问题，现在增加了一个字母 c，我们能不能用类似的方法做呢？设 $c_i$ 表示字母 c 在长度为 $i$ 的前缀里的出现次数，我们继续分析一下平衡子串的条件

$$
\begin{matrix}
a_r - a_{l - 1} = b_r - b_{l - 1} \
b_r - b_{l - 1} = c_r - c_{l - 1} \
\end{matrix}
$$

移项得

$$
\begin{matrix}
a_r - b_r = a_{l - 1} - b_{l - 1} \
b_r - c_r = b_{l - 1} - c_{l - 1} \
\end{matrix}
$$

因此，我们仍然可以用相同的做法求出平衡子串的最大长度，只不过哈希表的 key 不是一个整数 $(a_i - b_i)$，而是一个数对 $(a_i - b_i, b_i - c_i)$。

复杂度 $\mathcal{O}(n)$（认为字符集大小是常数）。

其实，这个做法也可以推广到任意字符集，复杂度 $\mathcal{O}(n|\Sigma| \times 2^{|\Sigma|})$，其中 $|\Sigma|$ 是字符集大小。有兴趣的读者可以试着做一下本题强化版 CF GYM100584D - Balanced strings，链接就不附了，怕扣子又把我帖子搞没了。

参考代码（c++）

class Solution {
public:
    int longestBalanced(string s) {
        int n = s.size(), ans = 0;

        // 子串只包含一个字母的情况
        auto calc1 = [&]() {
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                if (i == 0 || s[i] == s[i - 1]) cnt++;
                else cnt = 1;
                ans = max(ans, cnt);
            }
        };

        // 子串只包含两个字母的情况
        auto calc2 = [&](char a, char b) {
            unordered_map<int, int> mp;
            mp[0] = -1;

            // x 表示 a_i - b_i 的值
            int x = 0;
            for(int i = 0; i < n; i++) {
                if (s[i] == a) x++;
                else if (s[i] == b) x--;
                else {
                    // 遇到不在子串里的字符，截断
                    mp.clear();
                    x = 0;
                }
                if (mp.count(x)) ans = max(ans, i - mp[x]);
                else mp[x] = i;
            }
        };

        // 子串包含三个字母的情况
        auto calc3 = [&]() {
            unordered_map<long long, int> mp;
            mp[0] = -1;

            // x 表示 a_i - b_i 的值
            // y 表示 b_i - c_i 的值
            int x = 0, y = 0;
            for (int i = 0; i < n; i++) {
                if (s[i] == 'a') x++;
                else if (s[i] == 'b') x--, y++;
                else y--;
                // c++ 的 unordered_map 不支持用 pair 作为 key
                // 所以只能把数对映射成一个整数
                // 当然也可以直接用 map，用 pair 作为 key
                // 只是复杂度会乘上一个 log
                long long key = 10LL * x * n + y;
                if (mp.count(key)) ans = max(ans, i - mp[key]);
                else mp[key] = i;
            }
        };

        calc1();
        calc2('a', 'b');
        calc2('a', 'c');
        calc2('b', 'c');
        calc3();
        return ans;
    }
};

不会做怎么办

读者首先需要掌握用前缀和 + 哈希表的方式，求特定子数组数量或最大长度的方法。读者可以学习 灵神题单 - 常用数据结构 的“前缀和与哈希表”一节。

如果读者掌握了这一技巧，那么至少可以解答只包含 a 和 b 的情况。若此时仍然不会做本题，需要加强从特殊到一般的拓展能力。一般来说可以先考虑一个简化的问题怎么做（例如图上问题先想一下树上怎么做，树上问题先想一下链上怎么做，二维矩阵问题先想一下一维序列怎么做），这只能在大量的练习中慢慢习得。

解法：枚举 & 线段树 & 二分

简化问题

先考虑一个简化版的问题：求最长的子数组，使得其中偶数的数量等于奇数的数量。

这个简化版问题和上周的 leetcode 3714. 最长的平衡子串 II 非常相似：把奇数看成 $1$，偶数看成 $-1$，求的其实就是“最长的和为 $0$ 的子数组”。详见 leetcode 560. 和为 K 的子数组。

简单来说，这个问题可以用前缀和求解：设 $s_i$ 表示长度为 $i$ 的前缀的元素和，若子数组 $(l, r]$ 的元素和为 $0$，则有 $s_r - s_l = 0$，即 $s_l = s_r$。为了让子数组的长度 $(r - l)$ 最大，我们可以用哈希表维护每种 $s_l$ 对应的最小 $l$。

原问题

回到原问题。现在只统计不同的偶数和不同的奇数，怎么做？

首先，和子数组里的元素种数有关的题目，应该马上想到经典问题“luo 谷 P1972 - [SDOI2009] HH 的项链”：从左到右枚举子数组的右端点，对于每种数，只把它最近出现的位置设为 $\pm 1$，其它位置都设为 $0$。

这样，问题就变成了动态版的“求最长的和为 $0$ 的子数组”：给定一个序列，每次操作可能把一个 $0$ 变成 $\pm 1$，或把一个 $\pm 1$ 变成 $0$。每次询问给定一个前缀和目标值 $s_r$，找出 $s_l = s_r$ 的最小下标 $l$。

元素的修改可以用线段树来维护，可是最小下标该怎么找呢？其实，元素范围在 $[-1, 1]$ 里的序列有一个非常强的性质：由于每移动一位，前缀和的变化最多为 $1$，因此 在一个区间内，前缀和是连续的。

所以，我们只需要在线段树的每个节点上，记录当前区间的最小前缀和 $x$ 和最大前缀和 $y$，只要 $x \le s_r \le y$，那么区间内一定存在一个下标 $l$，满足 $s_l = s_r$。所以在线段树上二分，即可找到这个下标。详见参考代码。

复杂度 $\mathcal{O}(n\log n)$。

参考代码（c++）

class Solution {
public:
    int longestBalanced(vector<int>& nums) {
        int n = nums.size();

        // 线段树节点，记录当前区间前缀和的最小值与最大值
        struct Node {
            int mn, mx, lazy;

            void apply(int x) {
                mn += x;
                mx += x;
                lazy += x;
            }
        } tree[(n + 1) * 4 + 5];

        auto merge = [&](Node nl, Node nr) {
            return Node {
                min(nl.mn, nr.mn),
                max(nl.mx, nr.mx),
                0
            };
        };

        // 线段树建树
        auto build = [&](this auto &&build, int id, int l, int r) -> void {
            if (l == r) tree[id] = Node {0, 0, 0};
            else {
                int nxt = id << 1, mid = (l + r) >> 1;
                build(nxt, l, mid); build(nxt | 1, mid + 1, r);
                tree[id] = merge(tree[nxt], tree[nxt | 1]);
            }
        };

        // 懒标记下推
        auto down = [&](int id) {
            if (tree[id].lazy == 0) return;
            int nxt = id << 1;
            tree[nxt].apply(tree[id].lazy);
            tree[nxt | 1].apply(tree[id].lazy);
            tree[id].lazy = 0;
        };

        // 给区间 [ql, qr] 的前缀和都加上 qv
        auto modify = [&](this auto &&modify, int id, int l, int r, int ql, int qr, int qv) -> void {
            if (ql <= l && r <= qr) tree[id].apply(qv);
            else {
                down(id);
                int nxt = id << 1, mid = (l + r) >> 1;
                if (ql <= mid) modify(nxt, l, mid, ql, qr, qv);
                if (qr > mid) modify(nxt | 1, mid + 1, r, ql, qr, qv);
                tree[id] = merge(tree[nxt], tree[nxt | 1]);
            }
        };

        // 线段树上二分，求前缀和等于 qv 的最小下标
        auto query = [&](this auto &&query, int id, int l, int r, int qv) -> int {
            if (l == r) return l;
            down(id);
            int nxt = id << 1, mid = (l + r) >> 1;
            // 只要一个区间满足 mn <= qv <= mx，那么一定存在一个等于 qv 的值
            // 为了让下标最小，只要左子区间满足，就去左子区间里拿答案，否则才去右子区间拿答案
            if (tree[nxt].mn <= qv && qv <= tree[nxt].mx) return query(nxt, l, mid, qv);
            else return query(nxt | 1, mid + 1, r, qv);
        };

        build(1, 0, n);
        // now：目前的前缀和
        int ans = 0, now = 0;
        // mp[x]：元素 x 最近出现在哪个下标
        unordered_map<int, int> mp;
        // 枚举子数组右端点
        for (int i = 1; i <= n; i++) {
            int x = nums[i - 1];
            int det = (x & 1 ? 1 : -1);
            if (mp.count(x)) {
                // 元素 x 之前出现过了，把那个位置改成 0
                modify(1, 0, n, mp[x], n, -det);
                now -= det;
            }
            // 把元素 x 当前出现的位置改成 +-1
            mp[x] = i;
            modify(1, 0, n, i, n, det);
            now += det;
            int pos = query(1, 0, n, now);
            ans = max(ans, i - pos);
        }
        return ans;
    }
};

不会做怎么办

本题的综合性比较强，需要读者掌握大量套路，我们逐个分解。

首先，如果读者不会做简化问题（即去掉“不同”的限制），说明读者没有掌握用前缀和 + 哈希表的方式，求特定子数组数量或最大长度的方法。读者可以学习 灵神题单 - 常用数据结构 的“前缀和与哈希表”一节。

接下来，如果读者看到“子数组里的不同元素”，没有马上反映出对应套路，需要复习“luo 谷 P1972 - [SDOI2009] HH 的项链”，并额外练习以下题目：

• CF gym 104459 E - [SDCPC2019] BaoBao Loves Reading：可以转化为子数组的不同元素数目。
• leetcode 2916. 子数组不同元素数目的平方和 II：一道比较综合的题目。

最后，如果读者没有意识到“元素范围在 $[-1, 1]$ 内的序列，在一个区间内，前缀和是连续的”，我暂时没有找到直接相关的练习题。可以练习 leetcode 2488. 统计中位数为 K 的子数组 一题，允许存在相同元素的加强版，并尝试用线性复杂度解答。我的题解 可供参考。

解法：模拟

按题意模拟即可。复杂度 $\mathcal{O}(n)$。

参考代码（c++）

###cpp

class Solution {
public:
    vector<int> constructTransformedArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans;
        for (int i = 0; i < n; i++) {
            int j = (i + nums[i] % n + n) % n;
            ans.push_back(nums[j]);
        }
        return ans;
    }
};