能否通过指定操作从比特串A得到B的算法思路咨询

给定两个等长比特串A和B，判断是否可通过以下操作从A得到B：

• 选择两个索引i、j，要求两处比特值相同；
• i、j之间的区间内，1的数量大于区间外1的数量；
• 该区间内0的数量大于区间外0的数量；
• 翻转这两个索引处的比特。

操作示例 #

原比特串：0001010001
选中索引处的比特为0（标注加粗）：0001010001

• 区间内0的数量：3 > 区间外0的数量：2
• 区间内1的数量：2 > 区间外1的数量：1
  翻转后得到合法比特串：0101010101

尝试解法的问题 #

我尝试从右到左遍历，记录两侧的1和0数量，当右侧的1、0数量少于左侧时执行操作，试图将所有1移到右侧（将比特串转换为字典序最小的简化版本后与B的简化版本比较），但该方法无法通过隐藏测试用例，不确定算法思路是否正确。

必要条件检查（先快速排除不可能的情况） #

1. 1的数量奇偶性一致：每次操作要么将两个0翻转为1（1的数量+2），要么将两个1翻转为0（1的数量-2），因此A和B中1的数量必须满足 count1(A) ≡ count1(B) mod 2，否则直接判定不可行。
2. 差异位置数量为偶数：对比A和B的每个位置，统计不同比特的位置数（差异位置），该数量必须是偶数——因为每次操作仅改变两个位置的比特状态。
3. 比特数量匹配：若count1(B) > count1(A)，则A中0的数量必须至少为(count1(B)-count1(A))/2（需要翻转这么多对0为1）；反之，若count1(B) < count1(A)，则A中1的数量必须至少为(count1(A)-count1(B))/2。

核心操作限制的关键观察 #

操作要求的区间必须满足：

• 区间长度 > 总长度的一半（因为区间内的1和0数量都要大于区间外，即区间长度k > n-k → k > n/2）；
• 区间内包含超过一半的总1数，同时包含超过一半的总0数。

这意味着只有足够大的、覆盖了多数1和0的区间内的相同比特，才能被选中进行翻转。

充分条件判断 #

在满足必要条件的基础上，需验证：

1. 可配对的比特存在：
   • 若需要增加1的数量，A中必须存在至少(count1(B)-count1(A))/2对0，每对0所在的区间满足操作的数量要求；
   • 若需要减少1的数量，A中必须存在至少(count1(A)-count1(B))/2对1，每对1所在的区间满足操作的数量要求。
2. 差异位置可被操作覆盖：
   差异位置中，0→1（A是0、B是1）的数量必须等于需要翻转的0对数量×2，1→0（A是1、B是0）的数量必须等于需要翻转的1对数量×2。

为什么原思路错误 #

原思路试图将比特串转换为字典序最小的版本，但操作的本质是翻转相同比特的状态而非交换比特位置，无法实现任意调整比特的分布（比如不能直接将左侧的1移到右侧，只能通过翻转0为1或1为0来调整数量），因此字典序最小的简化逻辑不适用。

内容的提问来源于stack exchange，提问作者Joseph Bendy