2712. 使所有字符相等的最小成本

难度中等

给你一个下标从 0 开始、长度为 n 的二进制字符串 s ，你可以对其执行两种操作：

• 选中一个下标 i 并且反转从下标 0 到下标 i （包括下标 0 和下标 i ）的所有字符，成本为 i + 1 。
• 选中一个下标 i 并且反转从下标 i 到下标 n - 1 （包括下标 i 和下标 n - 1 ）的所有字符，成本为 n - i 。

返回使字符串内所有字符 相等 需要的 最小成本 。

反转 字符意味着：如果原来的值是 '0' ，则反转后值变为 '1' ，反之亦然。

示例 1：

输入：s = "0011"

输出：2

解释：执行第二种操作，选中下标 i = 2 ，可以得到 s = "0000" ，成本为 2 。可以证明 2 是使所有字符相等的最小成本。

示例 2：

输入：s = "010101"

输出：9

解释：执行第一种操作，选中下标 i = 2 ，可以得到 s = "101101" ，成本为 3 。
执行第一种操作，选中下标 i = 1 ，可以得到 s = "011101" ，成本为 2 。
执行第一种操作，选中下标 i = 0 ，可以得到 s = "111101" ，成本为 1 。
执行第二种操作，选中下标 i = 4 ，可以得到 s = "111110" ，成本为 2 。
执行第一种操作，选中下标 i = 5 ，可以得到 s = "111111" ，成本为 1 。
使所有字符相等的总成本等于 9 。可以证明 9 是使所有字符相等的最小成本。

提示：

• 1 <= s.length == n <= 10^5
• s[i] 为 '0' 或 '1'

# 前后缀分解

前后缀分解是分割数组分别为前缀和后缀两部分，最后枚举分割点计算总的

$pre[i][0]$ 将前缀变为 $0$ 的最小代价，$pre[i][1]$ 将前缀变为 $1$ 的最小代价

$pre[i][0]$

• $s[i] == '0'$

  • $pre[i][0] = pre[i - 1][0]$

• $s[i] == '1'$

  • $pre[i][0] = pre[i - 1][1] + i + 1$

    由于 $s[i] =='1'$，所以只能将 $i$ 前缀为 $1$ 的变为 $0$

    $i-1$ 变为 $1$ 的最小代价 + 当前代价

$pre[i][1]$

• $s[i] == '1'$

  • $pre[i][1] = pre[i - 1][1]$

• $s[i] == '0'$

  • $pre[i][1] = pre[i - 1][0] + i + 1$

同理也需要计算后缀

$suf[i][0]$ 将后缀变为 $0$ 的最小代价，$suf[i][1]$ 将后缀变为 $1$ 的最小代价

$suf[i][0]$

• $s[i] == '0'$

  • $suf[i][0] = suf[i - 1][0]$

• $s[i] == '1'$

  • $suf[i][0] = suf[i - 1][1] + i + 1$

    由于 $suf[i] =='1'$，所以只能将 $i$ 前缀为 $1$ 的变为 $0$

    $i-1$ 变为 $1$ 的最小代价 + 当前代价

$suf[i][1]$

• $s[i] == '1'$

  • $suf[i][1] = suf[i - 1][1]$

• $s[i] == '0'$

  • $suf[i][1] = suf[i - 1][0] + i + 1$

1. 一组操作的具体顺序不影响操作后的结果

2. 最优解中一个前缀翻转区间与一个后缀翻转区间必然没有交集，实际效果等于两个更小成本的两个翻转区间。所以最优方案一定可以划分成一组前缀操作和一组后缀操作，同时两组内的操作没有交集

class Solution {

    public long minimumCost(String s) {

        // 前缀

        long[][] pre = new long[n + 1][2];

        for (int i = 1; i <= n; i++) {

            if (s.charAt(i - 1) == '0') {

                pre[i][0] = pre[i - 1][0];

                // 将 i 及之前翻转为 0 的数翻转为 1

                pre[i][1] = pre[i - 1][0] + i;

            } else {

                pre[i][1] = pre[i - 1][1];

                // 将 i 及之前翻转为 0 的数翻转为 1

                pre[i][0] = pre[i - 1][1] + i;

            }

        }

        // 后缀

        long[][] suf = new long[n + 1][2];

        for (int i = n - 1; i >= 0; i--) {

            if (s.charAt(i) == '0') {

                suf[i][0] = suf[i + 1][0];

                suf[i][1] = suf[i + 1][0] + n - i;

            } else {

                suf[i][1] = suf[i + 1][1];

                suf[i][0] = suf[i + 1][1] + n - i;

            }

        }

        // 枚举分割点

        long ans = Long.MAX_VALUE;

        for (int i = 0; i < n; i++) {

            // 前后缀翻转为 0 的最小成本

            ans = Math.min(ans, pre[i + 1][0] + suf[i + 1][0]);

            ans = Math.min(ans, pre[i + 1][1] + suf[i + 1][1]);

        }

        return ans;

    }

}

# 贪心

对于 $000\,1111$

由于需要让所有字符相等，所以翻转可以全为 $1$ 或者全为 $0$。那么就可以贪心的选择所需要的操作次数少的一方

即：

• 选择 $000$，翻转为 $111$ 所需的操作次数为 $3$
• 选择 $1111$，翻转为 $0000$ 所需的操作次数为 $4$

对于 $0000\,11$，翻转只需将 $0000$ 翻转为 $1111$ 或者将 $11$ 翻转为 $00$

选择 $0000$ 翻转为 $1111$，若将 $\underline{00}00$ 变为 $\underline{11}00$ 则只会让操作次数变大，因为还需要翻转回来。

当前元素为 $i$，只需考虑 $s[i] \,!= s[i - 1]$ 部分。要么把 $i$ 前面的元素翻转为 $s[i]$，或者将 $i$ 以及后面的元素翻转为前面的元素。

此时 $i$ 前面部分已经全部相等。

而 $i$ 以后的部分翻转后性质是一样的

• 例如：$10010$ 翻转后 $01101$，此时相邻部分相等或者不相等更不反转一样

例如：$010101$

• $\underline{0}1\underline{0101}$：$0$ 变为 $1$

• $\underline{11}0\underline{101}$：$11$ 变为 $00$

• $\underline{000}1\underline{01}$：$000$ 变为 $111$

  也可以 $101$ 变为 $010$

• $\underline{1111}0\underline{1}$：将 $01$ 变为 $10$

• $\underline{11111}0$：$0$ 变为 $1$

class Solution {

    public long minimumCost(String s) {

        int n = s.length();

        long ans = 0;

        for (int i = 1; i < n; i++) {

            if (s.charAt(i) != s.charAt(i - 1)) {

                // 由于只需要变为相等，左右部分选择较小者

                ans += Math.min(i, n - i);

            }

        }

        return ans;

    }

}