| Codeforces Round 1135 (Div. 2) |
|---|
| Finished |
The diversity of a binary string $$$s$$$ is the number of distinct$$$^{\text{∗}}$$$ strings that can be obtained by performing the following operation at most once:
Choose an integer $$$0 \leq x \leq 1$$$ and two integers $$$1 \leq l \leq r \leq n$$$, and set $$$s_i := x$$$ for all $$$l \leq i \leq r$$$.
For example, the string 10 has diversity $$$3$$$ because the strings 10, 11, and 00. can be obtained.
You are given a string $$$s$$$ of length $$$n$$$ as well as an integer $$$k$$$. You are allowed to toggle the values of at most $$$k$$$ characters in the string. Your task is to determine the maximum possible diversity of the resulting string.
$$$^{\text{∗}}$$$Two strings $$$a$$$ and $$$b$$$ are distinct if there exists an index $$$i$$$ such that $$$a_i \neq b_i$$$.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.
The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$0 \leq k \leq n$$$) — the length of the string and the maximum number of characters you are allowed to toggle.
The second line of each test case contains a binary string $$$s$$$ of length $$$n$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.
For each test case, output a line with a single integer — the maximum possible diversity of the string after toggling at most $$$k$$$ characters.
41 104 410015 1111117 21101001
2111623
In the first test case, it is optimal to toggle the first character, resulting in the string 1 with a diversity of $$$2$$$.
In the second test case, the string 1111 achieves the maximum possible diversity of $$$11$$$.
| Name |
|---|


