题目

题目描述

给定仅由A和B构成的长度为N的字符串S和T。 可以执行若干次（可以不执行）以下操作： 选择一个1<=i<j<=N的整数i和j，将Si变为A，Sj变为B。 判断是否可以使S与T相同，如果可能，请输出所需要的最小操作次数，如果不行，输出-1

输入描述

第一行输入一个整数N第二行字符串S第三行字符串T

输出描述

判断是否可以使S与T相同，如果可能，请输出所需要的最小操作次数，如果不行，输出-1

样例1

输入

5

BAABA

AABAB

输出

2

样例2

输入

2

AB

BA

输出

-1

提示

2<=N<=200000

我的代码

#include<bits/stdc++.h>
using namespace std;
int n,ans;
string s,t;
bool ak[200005],bk[200005],a[200005],b[200005];
int main()
{
    cin>>n>>s>>t;
    for(int i=0;i<n;i++)
    {
        if(s[i]==t[i])
        {
            if(t[i]=='A')ak[i]=true;
            else bk[i]=true;
        }
        else
        {
            if(t[i]=='A')a[i]=true;
            else b[i]=true;
        }
    }
    for(int i=0;i<n;i++)
    {
        if(a[i]==true)
        {
            for(int j=i+1;j<n;j++)
            {
                if(b[j]==true)
                {
                    ans++;
                    a[i]=false;
                    ak[i]=true;
                    b[j]=false;
                    bk[j]=true;
                    break;
                }
                else if(bk[j]==true)
                {
                    ans++;
                    a[i]=false;
                    ak[i]=true;
                    break;
                }
            }
            if(a[i]==true)
            {
                cout<<"-1";
                return 0;
            }
        }
        else if(b[i]==true)
        {
            for(int j=i-1;j>=0;j--)
            {
                if(a[j]==true)
                {
                    ans++;
                    a[j]=false;
                    ak[j]=true;
                    b[i]=false;
                    bk[i]=true;
                    break;
                }
                else if(ak[j]==true)
                {
                    ans++;
                    b[i]=false;
                    break;
                }
            }
            if(b[i]==true)
            {
                cout<<"-1";
                return 0;
            }
        }
    }
    cout<<ans;
}

思路

ak数组是存储s和t中是否都是A，bk是存储s和t中是否都是B，a数组存储需要变为A的，b存储需要变为B的（例如s=ABAB,t=AABB,则ak={1,0,0,0},bk={0,0,0,1},a={0,1,0,0},b={0,0,1,0})）。遍历s和t,将ak,bk,a,b存储一遍。再次遍历，如果s[i]='A',t[i]='B',就看前面有没有a[j]或ak[j],有就ans++,再把ak,bk,a,b改一下，没有就输出-1。当s[i]='B',t[i]='A',就看后面有没有b[j]或bk[j]，同理做类似操作。最后输出ans；