CF1404A Balanced Bitstring

比特串是仅由字符 $0$ 和 $1$ 组成的字符串。如果一个比特串的任意长度为 $k$ 的子串中，$0$ 和 $1$ 的数量都相等（即各有 $\frac{k}{2}$ 个），则称该比特串为 $k$-平衡比特串。 现在给定一个整数 $k$ 和一个仅由字符 $0$、$1$ 和 $?$ 组成的字符串 $s$。你需要判断，是否可以通过将 $s$ 中的每个 $?$ 替换为 $0$ 或 $1$，使得最终得到的比特串是 $k$-平衡比特串。 如果字符串 $a$ 可以通过从字符串 $b$ 的开头删除若干（可能为零或全部）字符，并从结尾删除若干（可能为零或全部）字符得到，则称 $a$ 是 $b$ 的一个子串。

每组测试数据包含多个测试用例。第一行包含测试用例个数 $t$（$1 \le t \le 10^4$）。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $k$（$2 \le k \le n \le 3 \cdot 10^5$，$k$ 为偶数），分别表示字符串的长度和 $k$-平衡比特串的参数。 接下来一行包含字符串 $s$（$|s| = n$）。保证 $s$ 只包含 $0$、$1$ 和 $?$。 保证所有测试用例中 $n$ 的总和不超过 $3 \cdot 10^5$。

对于每个测试用例，如果可以将 $s$ 中的所有 $?$ 替换为 $0$ 或 $1$，使得最终得到的比特串是 $k$-平衡比特串，则输出 YES；否则输出 NO。

对于第一个测试用例，字符串本身已经是一个 $4$-平衡比特串。 对于第二个测试用例，字符串可以被替换为 101。 对于第四个测试用例，字符串可以被替换为 0110。 对于第五个测试用例，字符串可以被替换为 1100110。 由 ChatGPT 4.1 翻译