想了很久没思路，看了几个题解，自己尝试了一下。下面记录尝试的几种办法。
滑动窗口
按灵神的题解稍微改动了一下滑动窗口的写法，换成我熟悉的样子。拼接s为s+s，这样所有旋转后形成的字符串都变为了s+s的子串，分别对每个子串计算修改次数。计算修改次数这个在滑窗过程中维护，无需重复计算。
class Solution:def minFlips(self, s: str) -> int:# 所有旋转的结果都是s+s的子串n=len(s)a=list(map(int,s+s))# 对于s+s的长度为n的子区间进行固定长度的滑窗。# 假如对s+s根据其是否与0101匹配来标记的话，以s+s=110110为例，以*表示匹配，~表示不匹配为~***~~。# 当left为偶数时，*的数量表示不匹配0101需要修改的数目；~的数目表示不匹配1010需要修改的数目# 当left为奇数时，*的数量表示不匹配1010需要修改的数目；~的数目表示不匹配0101需要修改的数目# 无论如何，我们在子区间需要修改的永远是min(cnt,k-cnt),cnt为其中一个符号的统计ans=infcnt=left=0for i in range(2*n-1):# 获取当前的符号是否为要统计的符号，对当前符号计数。if a[i]%2==i%2:cnt+=1if i-left+1==n:ans=min(ans,cnt,n-cnt)# 如果出窗口的符号也是统计符号，那么统计符号减1if a[left]%2==left%2:cnt-=1left+=1return ans
DP
发现灵神题解下面有用动态规划写的，学习了一下。感觉dfs的写法比较直观易懂，用迭代的写法需要好好理解一下。
class Solution:def minFlips(self, s: str) -> int:a=list(map(int,s))n=len(s)# 如果字符串为偶数，匹配目标的首尾是不同的，没有办法通过操作1减少修改次数。无论是匹配1010，还是0101，其首与尾都不同，即使旋转，不匹配次数也不会发生改变（匹配对象仍然是0101，1010）# 如果字符串为奇数，匹配目标的首尾相同，能够允许一次两个相邻字符相同（可以通过旋转降低一次），所以问题变为了，允许一次重复的情况下的最少操作次数@cachedef dfs(i,pattern,k):# 操作次数小于0，无法操作，返回infif k<0:return inf# 到达尾端，返回0无需操作if i<0:return 0 # 如果直接匹配了，进行下一个if a[i]==pattern:return dfs(i-1,1-pattern,k)# 反之两种选择，要么使用操作2修改，要么选择操作1旋转，使用旋转之后k-1，之后就不允许再次旋转（因为旋转几次都等价1次）。取两者之间最少的return min(1+dfs(i-1,1-pattern,k),dfs(i-1,pattern,k-1))# 有两种匹配模式，选择其中最小的一个return min(dfs(n-1,0,n%2),dfs(n-1,1,n%2))
迭代写法:
class Solution:def minFlips(self, s: str) -> int:n=len(s)a=list(map(int,s))r=n%2# dp[i][k][p]表示在[0,i]上允许k+1个相同，以p结尾能得到的最小操作数dp=[[[inf]*2 for _ in range(r+1)] for _ in range(n)]for k in range(r+1):dp[0][k][0]=int(a[0]!=0)dp[0][k][1]=int(a[0]!=1)for i in range(n):ch=a[i]for k in range(r+1):for p in range(2):# 如果当前字符是所要求的字符，没有cost，否则为1costcost=0 if ch==p else 1# 当前以p结尾，上一个必须以1-p结尾dp[i][k][p]=min(dp[i][k][p],cost+dp[i-1][k][1-p]) if k>0:# 如果是在允许1次相邻的循环中，尝试在此位置允许重复，上一个仍为p加上当前改为p的costdp[i][k][p]=min(dp[i][k][p],dp[i-1][k-1][p]+cost)# 返回在[0,n-1],允许r次相邻以0，1结尾的最小值return min(dp[n-1][r][0],dp[n-1][r][1])