有两个字符串 \(S,T\)。每次操作可以将 \(S\) 中某个字符移到开头或结尾。若想要 \(S=T\) ，则需要的最少操作次数是多少。\(Q \leq 100, n\leq 100\)

Solution

考虑贪心，我们要找一个串，它是 \(S\) 的子序列，\(T\) 的子串，并且长度最大

于是我们暴力枚举这个串在 \(T\) 中的开头位置，然后扫一遍 \(S\) 即可

#include <bits/stdc++.h>
using namespace std;

int T,n,p[26];
char s[105],t[105];

signed main() {
    ios::sync_with_stdio(false);
    cin>>T;
    while(T--) {
        cin>>n>>s+1>>t+1;
        int ans=0;
        memset(p,0,sizeof p);
        for(int i=1;i<=n;i++) {
            p[s[i]-'a']++;
            p[t[i]-'a']--;
        }
        if(*max_element(p,p+26)||*min_element(p,p+26)) {
            cout<<-1<<endl;
            continue;
        }
        for(int i=1;i<=n;i++) {
            int cnt=0,pos=1;
            for(int j=i;j<=n;j++) {
                while(s[pos]!=t[j]&&pos<=n) ++pos;
                if(pos>n) break;
                ++pos; ++cnt;
            }
            ans=max(ans,cnt);
        }
        cout<<n-ans<<endl;
    }
}