思路：思维

相邻字符连续删除的场景，这是一个典型的栈的应用。

所以用栈这么操作后，在栈中的元素必然是 101010... 或者 010101... 这样的

这部分元素我们考虑修改，现在令栈中的元素构成的串为 $t$ 。

$t$ 的长度为偶数，则修改 $\frac{t}{2}$ 个即可。

$t$ 的长度为奇数，则必然是 1010...101 ，那么 '0' 的个数比 '1' 的个数少 $1$ 。至多修改 $\lfloor\frac{t}{2}\rfloor$ 即可。

考虑需要修改的次数为 $cnt$ ，实际修改的次数为 $k$

$k\leq cnt$ ，则可以通过合适的修改后，可以再删除 $2k$ 个 。
$k > cnt$ ，则修改 $cnt$ 个后，可以再删除 $2cnt$ 个。

那么我们还需要修改 $k - cnt$ 次 。

• 如果这个 $k-cnt$ 是偶数，那么怎么修改都可以

• 如果这个 $k-cnt$ 是奇数，那么相当于还需要修改 $1$ 次 。

  如果原串长度是奇数，那么再怎么删除都会剩下至少一个字符，所以把这 $k-cnt$ 修改那个剩下的字符即可。

  如果原串长度是偶数，那么也只需要修改一个字符，此时必然是剩下两个字符。

时间复杂度：$O(n)$

代码

Python

n, k = map(int, input().split())
s = input()

stk = []
for i in s:
    x = int(i)
    if len(stk) == 0 or stk[-1] != x:
        stk.append(x)
    else:
        stk.pop()

res = len(stk)

cnt = len(stk) // 2
if cnt >= k:
    res -= k * 2
elif cnt < k:
    res -= cnt * 2

    # 可以全部转换一样的，但是需要考虑几种情况
    # 如果剩余字符数是奇数，那么必然是一个，剩余的修改次数均给这个字符即可
    if res & 1:
        pass
    else:
        # 否则剩余字符数为0，还有 k-cnt 次需要修改
        # 如果这个是奇数，那么必然不行
        # 如果是偶数，那么只要对一个字符修改偶数次即可
        ch = k - cnt
        if ch & 1:
            res += 2

print(res)

C++

#include<iostream>
#include<stack>
using namespace std;
int main(){
    stack<char> st;
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++){
        char c;
        cin>>c;
        if(!st.empty()&&st.top()==c){
            st.pop();
        }
        else st.push(c);
    }
    int cnt=st.size()/2;
    int ans=0;
    int size=st.size();
    if(k<=cnt){
        ans=size-k*2;
    }
    else{
        if(size%2){
            ans=1;
        }
        else{
            int rest=(k-cnt);
            if(rest%2){
                ans=2;
            }
        }
    }
    printf("%d\n",ans);
}

Java

import java.util.Scanner;
import java.util.Stack;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n, k;
        n = sc.nextInt();
        k = sc.nextInt();
        String s = sc.next();
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < n; i++){
            if(stack.isEmpty()){
                stack.add(s.charAt(i));
                continue;
            }
            char ch = s.charAt(i);
            char ch1 = stack.lastElement();
            if (ch == ch1) {
                stack.pop();
            } else {
                stack.add(ch);
            }
        }
        int length = stack.size();
        int min = length / 2;
        if (k < min){
            System.out.println(length - 2 * k);
        } else if (k == min){
            System.out.println(length % 2);
        } else {
            k -= min;
            if (length % 2 == 1){
                System.out.println(1);
            } else {
                if (k % 2 == 0) {
                    System.out.println(0);
                } else {
                    System.out.println(2);
                }
            }
        }
        sc.close();
    }
}

题目描述

小美有一个 $01$ 串 $s$，当串中相邻字符相同时，可以将这两个相邻字符删除，得到一个新的串。一直删除到串中相邻字符均不相同。

现在，小美对这个串修改了恰好 $k$ 次，一次修改可以将 '1' 修改为 '0' ，或者将 '0' 修改为 '1' 。

现在，小美想问你，将 $s$ 修改恰好 $k$ 次后，再进行删除操作，最终串的长度最短为多少？

输入描述

第一行，两个正整数 $n,k(1 \leq k \leq n \leq 10^5)$，表示字符串 $s$ 的长度和修改次数。

第二行，一个长度为 $n$ 的字符串 $s$ ，保证 $s$ 的字符要么是 '0' ，要么是 '1'

输出描述

$k$ 次修改后进行删除，最终串的长度最小值。

样例

输入

4 1
1010

输出

2

说明

将第二个字符修改为 '1'，然后最终的串为 "10"

样例2

输入

6 3
101111

输出

0

说明

修改第一个，第三个，第四个字符为 '0' ，最终相邻字符删除，最终的串中字符均可以删除。

串成为一个空串。