约束无连续三位相同比特时，二进制字符串匹配的最少翻转次数

问题描述 #

给定两个等长二进制字符串a和b，初始时两者均无连续三位相同比特，b不可修改。每次仅能翻转a的一个比特，转换过程中a始终不能出现连续三位相同比特（000或111），求将a转为b的最少翻转次数。

解决思路：动态规划+状态跟踪 #

由于约束仅与连续三位比特相关，我们可以通过动态规划跟踪当前字符串的最后两位状态，同时考虑是否已匹配b的对应位，确保转换过程全程合法。

状态定义 #

定义dp[i][x][y][f]为：处理到字符串第i位（索引从0开始）时，第i-1位为x、第i位为y，f标记前i位是否完全匹配b的前i位（f=1表示完全匹配，f=0表示未完全匹配），此时从a转换到该状态的最少翻转次数。其中x和y的取值只能是0或1，且整个字符串到第i位为止无连续三位相同比特。

初始化 #

1. 长度为1的情况：直接返回0（若a[0]==b[0]）或1（若a[0]!=b[0]），无连续三位约束。
2. 长度>=2的情况：
   枚举前两位的所有合法组合(x,y)，计算翻转次数：

   dp[1][x][y][1] = (a[0] != x) + (a[1] != y)  // 前两位完全匹配b的情况
   dp[1][x][y][0] = (a[0] != x) + (a[1] != y)  // 前两位未完全匹配b的情况
   

   两位组合不存在连续三位问题，所有组合均合法。

状态转移 #

对于i >= 2，分两种情况处理：

情况1：当前状态前i位未完全匹配b

遍历所有可能的前状态(prev_x, prev_y, f_prev)，枚举当前位的可能取值curr_y：

1. 合法性检查：若prev_x == prev_y == curr_y，则该组合为连续三位相同，跳过此状态。
2. 计算翻转次数：
   新状态的翻转次数为前状态的次数加上翻转第i位的代价（若a[i] != curr_y则加1，否则加0）。同时标记新状态是否完全匹配b：若prev_x == b[i-1]且curr_y == b[i]且f_prev ==1，则f_new=1，否则f_new=0。

情况2：当前状态前i位已完全匹配b

此时第i-2位为b[i-2]、第i-1位为b[i-1]，当前位为b[i]，需确保b[i-2], b[i-1], b[i]合法（题目已保证初始b无连续三位相同，故此状态天然合法），翻转次数为前匹配状态的次数加上必要的翻转代价。

最终结果 #

当处理完所有位（i = n-1，n为字符串长度），取dp[n-1][b[n-2]][b[n-1]][1]的值，即为将a完全转换为b的最少翻转次数。

示例验证

以a=0011，b=0101（n=4）为例：

1. 初始状态无法直接翻转a[1]得到0111（非法），需通过过渡状态：
   • 翻转a[3]得到0010（合法），翻转次数+1
   • 翻转a[1]得到0110（合法），翻转次数+1
   • 翻转a[2]得到0100（合法），翻转次数+1
   • 翻转a[3]得到0101（合法），翻转次数+1
2. 动态规划会捕捉到这条合法路径，最终得到最少翻转次数为4，与示例输出一致。

备选思路：BFS最短路径 #

对于较短的字符串，可直接用BFS求解：

• 每个节点为合法字符串（无连续三位相同）
• 边为翻转一个比特得到的另一个合法字符串
• 从a出发，找到到达b的最短路径长度，即为最少翻转次数。

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