算法1

(暴力枚举) $O(n)$

我们通过贪心 每次找前两个位置不相同 那么就翻转连续片段

时间复杂度

参考文献

C++ 代码

#include<bits/stdc++.h>

using namespace std;

int main()
{
    string a, b;
    cin >> a >> b;
    int before = -1, sum=0;
    for(int i=0;i<a.size();i++)
    {
        if(a[i]!=b[i]&&before== -1)
        {
            before=i;
        }
        else if(a[i]!=b[i] && before != -1)
        {
            sum+=i-before;
            before= - 1;
        }
    }
    cout<<sum<<endl;
}