题解 | 宝石手串

可以把这题理解成寻找字符串中最近相同字符 没有相同字符就输出-1 有的话就输出最近距离

注意的点：

1、环形结构 所以将两个s拼接在一起进行寻找

2、n个宝石 最多只能去掉n-2个 如果去掉的个数大于n-2个就说明要输出-1了

3、用unordered_map来存储字符和对应下表 将s中字符挨个插入其中 边插便寻找是否已经存在相同字符 并更新相同字符最短举例

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    int T;
    cin >> T;
    while(T--) {
        int n;
        cin >> n;
        string s;
        cin >> s;
        unordered_map<char, int> m;
        if(n == 2) {
            cout << (s[0]==s[1] ? 0 : -1) << endl;
            continue;
        } 
        s = s + s;
        int min_len = 2 * n;
        for(int i = 0; i < 2 * n; ++i) {
            if(m.find(s[i]) == m.end()) m[s[i]] = i;
            else {
                auto it = m.find(s[i]);
                min_len = min(min_len, i - 1 - it->second);
                it->second = i;
            }
        }
        cout << (min_len >= n-1 ? -1 : min_len) << endl;
    }
    return 0;
}