我们可以将所有类型 \(2\) 的操作安排在类型 \(1\) 的操作之前。因为类型 \(2\) 的操作是反转任意一个字符,而类型 \(1\) 的操作只会改变字符的相对顺序,不会改变字符的值。
当 \(n\) 是偶数时,交替字符串只可能为 \(0101\cdots 01\) 或者 \(1010 \cdots 10\) 的形式。
如果 \(n\) 是奇数,那么交替字符串为 \(0101 \cdots 010\) 或者 \(1010 \cdots 101\) 的形式。
我们首先考虑 \(0101 \cdots 010\),如果在所有类型 \(2\) 的操作完成后,\(s\) 可以通过类型 \(1\) 的操作得到该字符串,那么:
要么 \(s\) 就是 \(0101 \cdots 010\);
要么 \(s\) 是 \(01 \cdots 010 | 01 \cdots 01\) 的形式,或者是 \(10 \cdots 10|01 \cdots 010\) 的形式。这里我们用竖线 \(|\) 标注了类型 \(1\) 的操作,在 \(|\) 左侧的字符通过类型 \(1\) 的操作被移动到字符串的末尾,最终可以得到 \(0101 \cdots 010\)。
因此,\(s\) 要么是一个交替字符串(即 \(0101 \cdots 010\)),要么由两个交替字符串拼接而成,其中左侧的交替字符串以 \(0\) 结尾,右侧的交替字符串以 \(0\) 开头。
同理,如果我们考虑 \(1010 \cdots 101\),那么 ss 要么就是 \(1010 \cdots 101\),要么由两个交替字符串拼接而成,其中左侧的交替字符串以 \(1\) 结尾,右侧的交替字符串以 \(1\) 开头。
我们用 \(\textit{pre}[i][j]\)表示对于字符串的前缀 \(s[0..i]\),如果我们希望通过类型 \(2\) 的操作修改成「以 \(j\) 结尾的交替字符串」,那么最少需要的操作次数。这里 \(j\) 的取值为 \(0\) 或 \(1\)。根据定义,有递推式:
\[\begin{cases} \textit{pre}[i][0] = \textit{pre}[i-1][1] + (s[i] =='1') \\ \textit{pre}[i][1] = \textit{pre}[i-1][0] + (s[i] == '0') \end{cases} \]同理,我们用 \(\textit{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} \]答案可以为 \(\textit{pre}[n-1][0]\)或者 \(\textit{pre}[n-1][1]\),对应着将 \(s\) 本身变为一个交替字符串;
如果 \(n\) 是偶数,我们无需求出 \(\textit{suf}\)。
如果 \(n\) 是奇数,那么答案还可以为 \(\textit{pre}[i][0] + \textit{suf}[i+1][0]\) 以及 \(\textit{pre}[i][1] + \textit{suf}[i+1][1]\),对应着将 \(s\) 变为两个交替字符串的拼接。
所有可供选择的答案中的最小值即为类型 \(2\) 的操作的最少次数。
class Solution { public: static const int N=1e5+10; int pre[N][2],suf[N][2]; int minFlips(string s) { int n=s.size(); for(int i=1;i<=n;i++) { pre[i][0]=pre[i-1][1]+(s[i-1] == '1'); pre[i][1]=pre[i-1][0]+(s[i-1] == '0'); } int ans=min(pre[n][0],pre[n][1]); if(n & 1) { for(int i=n;i;i--) { suf[i][0]=suf[i+1][1]+(s[i-1] == '1'); suf[i][1]=suf[i+1][0]+(s[i-1] == '0'); ans=min(ans,pre[i][0]+suf[i+1][0]); ans=min(ans,pre[i][1]+suf[i+1][1]); } } return ans; } };