1888-使二进制字符串字符交替的最少反转次数

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:24 2023-09-13 16:06:24 Updated    

给你一个二进制字符串 s 。你可以按任意顺序执行以下两种操作任意次：

  • 类型 1 ：删除 字符串 s 的第一个字符并将它 添加 到字符串结尾。
  • 类型 2 ：选择 字符串 s 中任意一个字符并将该字符 反转 ，也就是如果值为 '0' ，则反转得到 '1' ，反之亦然。

请你返回使 s 变成 交替 字符串的前提下， 类型 2 的 最少 操作次数 。

我们称一个字符串是 交替 的，需要满足任意相邻字符都不同。

  • 比方说，字符串 "010" 和 "1010" 都是交替的，但是字符串 "0100" 不是。

示例 1：

**输入：** s = "111000"
**输出：** 2
**解释：** 执行第一种操作两次，得到 s = "100011" 。
然后对第三个和第六个字符执行第二种操作，得到 s = "10 **1** 01 **0** " 。

示例 2：

**输入：** s = "010"
**输出：** 0
**解释：** 字符串已经是交替的。

示例 3：

**输入：** s = "1110"
**输出：** 1
**解释：** 对第二个字符执行第二种操作，得到 s = "1 **0** 10" 。

提示：

  • 1 <= s.length <= 105
  • s[i] 要么是 '0' ，要么是 '1' 。

方法一：分析 + 前缀和 + 后缀和

提示 1

我们可以将所有类型 2 的操作安排在类型 1 的操作之前。

提示 1 解释

由于类型 2 的操作是反转任意一个字符，而类型 1 的操作只会改变字符的相对顺序，不会改变字符的值。因此如果我们想要修改某个字符，随时都可以修改。这样我们就可以把所有类型 2 的操作安排到最前面。

提示 2

设字符串 s 的长度为 n。

如果 n 是偶数，那么在所有类型 2 的操作完成后，s 已经是一个交替字符串了。

提示 2 解释

当 n 是偶数时，交替字符串只可能为 0101\cdots 01 或者 1010 \cdots 10 的形式。对这两个字符串进行类型 2 的操作，只会在它们之间相互转换。

类型 2 的操作是可逆的，这说明交替字符串只可能由交替字符串通过类型 2 的操作得来。因此，在所有类型 2 的操作完成后，s 必须是一个交替字符串。

提示 3

如果 n 是奇数，那么交替字符串为 0101 \cdots 010 或者 1010 \cdots 101 的形式。

我们首先考虑 0101 \cdots 010，如果在所有类型 2 的操作完成后，s 可以通过类型 2 的操作得到该字符串，那么：

  • 要么 s 就是 0101 \cdots 010；

  • 要么 s 是 01 \cdots 010 | 01 \cdots 01 的形式，或者是 10 \cdots 10|01 \cdots 010 的形式。这里我们用竖线 | 标注了类型 2 的操作，在 | 左侧的字符通过类型 2 的操作被移动到字符串的末尾，最终可以得到 0101 \cdots 010。

因此，s 要么是一个交替字符串（即 0101 \cdots 010），要么由两个交替字符串拼接而成，其中左侧的交替字符串以 0 结尾，右侧的交替字符串以 0 开头。

同理，如果我们考虑 1010 \cdots 101，那么 s 要么就是 1010 \cdots 101，要么由两个交替字符串拼接而成，其中左侧的交替字符串以 1 结尾，右侧的交替字符串以 1 开头。

思路与算法

我们用 pre}[i][j] 表示对于字符串的前缀 s[0..i]，如果我们希望通过类型 2 的操作修改成「以 j 结尾的交替字符串」，那么最少需要的操作次数。这里 j 的取值为 0 或 1。根据定义，有递推式：

\begin{cases}
\textit{pre}[i][0] = \textit{pre}[i-1][1] + \mathbb{I}(s[i], 1) \
\textit{pre}[i][1] = \textit{pre}[i-1][0] + \mathbb{I}(s[i], 0)
\end{cases}

其中 \mathbb{I}(x, y) 为示性函数，如果 x=y，那么函数值为 1，否则为 0。例如 \mathbb{I}(s[i], 1) 就表示：如果 s[i] 为 1，那么我们需要通过类型 2 的操作将其修改为 0，否则无需操作。

同理，我们用 suf}[i][j] 表示对于字符串的后缀 s[i..n-1]，如果我们希望通过类型 2 的操作修改成「以 j 开头的交替字符串」，那么最少需要的操作次数。这里 j 的取值为 0 或 1，同样有递推式：

\begin{cases}
\textit{suf}[i][0] = \textit{suf}[i+1][1] + \mathbb{I}(s[i], 1) \
\textit{suf}[i][1] = \textit{suf}[i+1][0] + \mathbb{I}(s[i], 0)
\end{cases}

在求解完数组 pre 和 suf 后：

  • 答案可以为 pre}[n-1][0] 或者 pre}[n-1][1]，对应着将 s 本身变为一个交替字符串；

  • 如果 n 是奇数，那么答案还可以为 pre}[i][0] + \textit{suf}[i+1][0] 以及 pre}[i][1] + \textit{suf}[i+1][1]，对应着将 s 变为两个交替字符串的拼接。

所有可供选择的答案中的最小值即为类型 2 的操作的最少次数。

细节

如果 n 是偶数，我们无需求出 suf。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    int minFlips(string s) {
        // 示性函数
        auto I = [](char ch, int x) -> int {
            return ch - '0' == x;
        };
        
        int n = s.size();
        vector<vector<int>> pre(n, vector<int>(2));
        // 注意 i=0 的边界情况
        for (int i = 0; i < n; ++i) {
            pre[i][0] = (i == 0 ? 0 : pre[i - 1][1]) + I(s[i], 1);
            pre[i][1] = (i == 0 ? 0 : pre[i - 1][0]) + I(s[i], 0);
        }
        
        int ans = min(pre[n - 1][0], pre[n - 1][1]);
        if (n % 2 == 1) {
            // 如果 n 是奇数，还需要求出 suf
            vector<vector<int>> suf(n, vector<int>(2));
            // 注意 i=n-1 的边界情况
            for (int i = n - 1; i >= 0; --i) {
                suf[i][0] = (i == n - 1 ? 0 : suf[i + 1][1]) + I(s[i], 1);
                suf[i][1] = (i == n - 1 ? 0 : suf[i + 1][0]) + I(s[i], 0);
            }
            for (int i = 0; i + 1 < n; ++i) {
                ans = min(ans, pre[i][0] + suf[i + 1][0]);
                ans = min(ans, pre[i][1] + suf[i + 1][1]);
            }
        }
        
        return ans;
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def minFlips(self, s: str) -> int:
        # 示性函数
        I = lambda ch, x: int(ord(ch) - ord("0") == x)
        
        n = len(s)
        pre = [[0, 0] for _ in range(n)]
        # 注意 i=0 的边界情况
        for i in range(n):
            pre[i][0] = (0 if i == 0 else pre[i - 1][1]) + I(s[i], 1)
            pre[i][1] = (0 if i == 0 else pre[i - 1][0]) + I(s[i], 0)
        
        ans = min(pre[n - 1][0], pre[n - 1][1])
        if n % 2 == 1:
            # 如果 n 是奇数，还需要求出 suf
            suf = [[0, 0] for _ in range(n)]
            # 注意 i=n-1 的边界情况
            for i in range(n - 1, -1, -1):
                suf[i][0] = (0 if i == n - 1 else suf[i + 1][1]) + I(s[i], 1)
                suf[i][1] = (0 if i == n - 1 else suf[i + 1][0]) + I(s[i], 0)
            
            for i in range(n - 1):
                ans = min(ans, pre[i][0] + suf[i + 1][0])
                ans = min(ans, pre[i][1] + suf[i + 1][1])
        
        return ans

复杂度分析

  • 时间复杂度：O(n)，其中 n 是字符串 s 的长度。

  • 空间复杂度：O(n)，即为数组 pre 和 suf 需要使用的空间。我们可以将空间复杂度优化至 O(1)，但这样写出的代码并不直观，因此本题解中不给出空间复杂度最优的写法。

 Comments
On this page
1888-使二进制字符串字符交替的最少反转次数