题解 | 宝石手串

//1. 弄一个函数专门解决这个这个问题
// 函数里面 1.1 输入n 和宝石
// 1.2 如果n 为2
// 1.3 如果 原手串已经断开
// 1.4 收集每个属性所在的位置，二维的
// 1.5 找到位置例如a[0,4] 顺序用位置4-0-1 逆序更近的话，用逆序，涉及到最小，前面就需要申请最大
//2. 弄一个输出
#include<bits/stdc++.h>
using namespace std;
int solve(){
    int n;
    cin >>n;
    string s;
    cin >> s;
    if(n==2){
        return (s[0]==s[1])? 0:-1;
    }
    // 1.3 如果原本的手串已经断开了
    for(int i = 0;i<n;i++){
        if(s[i] == s[(i+1)%n]){
            return 0;
        }
    }
    // 1.4 收集每个属性
    vector<vector<int>>weiz(26);
    for(int i = 0;i<n;i++){
        weiz[s[i] - 'a'].push_back(i);
    }
    // 1.5  找到位置例如a[0,4] 顺序用位置4-0-1 逆序更近的话，用逆序，涉及到最小，前面就需要申请最大
    int minn = n;
    for(int i = 0;i<26;i++){
        if(weiz[i].size() <=1){
            continue;
        }
        auto &p = weiz[i];
        int m = p.size();
         int ans = 0;
        for(int i = 0;i<m;i++){
           
            int j = (i+1)%m;
            if(i<j){
                ans = p[j] - p[i] - 1;
            }
            else{
                ans = p[j]+n - p[i]-1;
            }
            minn = min(minn,ans);
        }
    }
    if(minn == n) return -1;
    return minn;
}
int main(){
    int T;
    cin >> T;
    while(T--){
        cout << solve() << endl;
    }
    return 0;
}