题解

思路

一种合法替换唯一对应一个长度为 $K$ 的全 1 区间。

做法

设原串中 1 的总数为 $M$，起点为 $l$ 的区间可行，当且仅当区间内没有 0，并且区间内恰好包含原串全部 $M$ 个 1；此时区间内的 ? 必须填为 1，区间外的 ? 必须填为 0，所以替换方式也唯一。依次统计每个长度为 $K$ 的窗口中 0 和 1 的数量，恰有一个窗口可行时输出 Yes。

复杂度

第一个窗口直接统计，窗口右移时只删除左端字符并加入新的右端字符，因此每组数据的时间复杂度为 $O(N)$，空间复杂度为 $O(1)$。