题解 | 宝石手串

#include <climits>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<pair<int, string>> vec(n);//store input data
    int num;
    string str;
    for (int i = 0; i < n; ++i) { //赋值给vec
        cin >> num;
        cin >> str;
        vec[i].first = num;
        vec[i].second = str;
    }

    for (int i = 0; i < n; ++i) {
        int min_gap = INT_MAX;
        for (char c = 'a'; c <= 'z'; ++c) { //本来想暴力破解，奈何运行时间超出要求，那就遍历26个字母了
            char loc = c;
            vector<int> subscript; //用于存放字母的下标
            for (int j = 0; j < vec[i].first; ++j) {
                if ( loc == vec[i].second[j])
                    subscript.push_back(j); //存入字母下标
            }
            if (subscript.size() == 0 || subscript.size() == 1 )
                continue; //无该字母或只有一个该字母，无须执行之后操作
            for (int k = 0; k < subscript.size() - 1; ++k) {
                int a = subscript[k + 1] - subscript[k] - 1;
                min_gap = min(min_gap, a );
            }
            int b = subscript[0] + vec[i].first - subscript[subscript.size() - 1] - 1;//环形字母间隔
            if (b < min_gap)
                min_gap = b;
            if (min_gap == 0) //如果存在两相同字母紧挨，则排斥，无须之后继续遍历当下字符串
                break;
        }
        if (min_gap == INT_MAX)
            cout << -1 << endl;
        else
            cout << min_gap << endl;
    }
    return 0;
}