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

难度: Medium

给你一个下标从 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⁵
s[i] 为 '0' 或 '1'

Submission

运行时间: 94 ms

内存: 16.5 MB

class Solution:
    def minimumCost(self, s: str) -> int:
        if len(s) == 1:
            return 0
        # 分为左右两部分，如果长度为奇数，中间部分特殊处理
        n = len(s)
        mid = n >> 1
        ans = 0
        for sub in s[:mid], s[-1:-mid-1:-1]:
            for i in range(1, mid):
                if sub[i] != sub[i - 1]:
                    ans += i

        if s[mid] != s[mid - 1]:
            ans += mid
        if n & 1 and s[mid] != s[mid + 1]:
            ans += mid

        return ans

Explain

此题解的思路是将字符串分为左右两部分进行处理。对于每一部分，遍历字符串，比较相邻字符是否相等。如果不相等，就累加当前下标作为成本。对于长度为奇数的字符串，中间的字符需要特殊处理。最后将所有成本累加得到最小成本。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def minimumCost(self, s: str) -> int:
        if len(s) == 1:
            return 0
        # 分为左右两部分，如果长度为奇数，中间部分特殊处理
        n = len(s)
        mid = n >> 1
        ans = 0
        for sub in s[:mid], s[-1:-mid-1:-1]:
            for i in range(1, mid):
                if sub[i] != sub[i - 1]:
                    ans += i

        if s[mid] != s[mid - 1]:
            ans += mid
        if n & 1 and s[mid] != s[mid + 1]:
            ans += mid

        return ans

Explore

在处理长度为奇数的字符串时，中间的字符没有对称的字符与之匹配，因此它的处理不能简单地归入左半部分或右半部分。这个字符可能需要与它前后的字符进行比较来确定是否需要改变以达到最终目标，即所有字符相等。因此，中间的字符成为了一个特殊的分界点，需要独立考虑它与左右相邻字符的关系来计算额外的成本。

题解中的处理方式是将字符串从中间分割开，如果字符串长度为偶数，则可以平均分为两部分。如果长度为奇数，则中间的字符单独处理，左半部分包含从开始到中间字符前的部分，右半部分则是从字符串末尾到中间字符后的部分。这种分法允许在遍历时同时从头部和尾部向中间进行，简化了比较和成本计算的过程。

累加当前下标作为成本的方式是一种简化的方法，实际上它假设了每一步操作的成本与当前位置的下标成正比。这种设定主要是为了反映越靠近字符串中心的改变成本可能越高的假设。虽然这不完全准确地反映了所有可能的场景，但它提供了一种计算上的便利和直观的理解方式，特别是在没有具体每步操作成本的详细信息时。

在遍历字符串并比较相邻字符时，通过增加下标值来计算成本是一种抽象的模拟方式。这种计算方法假设修改字符的成本与其在字符串中的位置有关，即位置越靠近中心，修改的成本越高。这样的设定可能是为了模拟实际情况中，修改靠近中心的字符可能会影响更多的其他操作或者需要更多的步骤来保持整体的平衡。