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 <= 105
s[i] 为 '0' 或 '1'

请看视频讲解第三题，欢迎点赞！

提示 1

如果 s[i-1]\ne s[i]，那么必须反转，不然没法都相等：

要么翻转 s[0] 到 s[i-1]，成本为 i；
要么翻转 s[i] 到 s[n-1]，成本为 n-i。

这两种情况取最小值。

提示 2

从左到右遍历 s，如果 s[i-1]\ne s[i]，那么必须反转，规则同上。

反转后：

s[i] 及其左边的字符，都已经相等了。
s[i] 右边的每对相邻字符，反转前不同的，反转后仍然不同。所以要继续反转。

所以累加每次反转的成本，即为答案。

[sol-Python3]class Solution:
    def minimumCost(self, s: str) -> int:
        return sum(min(i, len(s) - i) for i, (x, y) in enumerate(pairwise(s), 1) if x != y)

[sol-Java]class Solution {
    public long minimumCost(String S) {
        long ans = 0;
        char[] s = S.toCharArray();
        int n = s.length;
        for (int i = 1; i < n; i++)
            if (s[i - 1] != s[i])
                ans += Math.min(i, n - i);
        return ans;
    }
}

[sol-C++]class Solution {
public:
    long long minimumCost(string s) {
        long long ans = 0;
        int n = s.length();
        for (int i = 1; i < n; i++)
            if (s[i - 1] != s[i])
                ans += min(i, n - i);
        return ans;
    }
};

[sol-Go]func minimumCost(s string) (ans int64) {
	n := len(s)
	for i := 1; i < n; i++ {
		if s[i-1] != s[i] {
			ans += int64(min(i, n-i))
		}
	}
	return
}

func min(a, b int) int { if b < a { return b }; return a }

[sol-JavaScript]var minimumCost = function (s) {
    const n = s.length;
    let ans = 0;
    for (let i = 1; i < n; i++)
        if (s[i - 1] !== s[i])
            ans += Math.min(i, n - i);
    return ans;
};

复杂度分析

时间复杂度：\mathcal{O}(n)，其中 n 为 s 的长度。
空间复杂度：\mathcal{O}(1)。仅用到若干额外变量。