题解 | 宝石手串

//  #牛客春招刷题训练营# https://www.nowcoder.com/discuss/726480854079250432
//  题目等价于求给定循环字符串中的相同字母间的最小间距
//  循环字符串可以把字符串 *= 2，不过此处没有这样
#include <climits>
#include <iostream>
#include <vector>
using namespace std;

void solve(){
  int n;
  cin >> n;
  string s;
  cin >> s;
  vector<int> a[26];//--------记录相同字母在字符串中的索引用于计算间距
  for (int i = 0; i < n; i++){
    a[s[i] - 'a'].push_back(i);
  }
  int ans = INT_MAX;
  for (int i = 0; i < 26; i++){
    if (a[i].empty()) continue;
    int size = a[i].size();
    for (int j = 0; j < size - 1; j++){
      ans = min(ans, a[i][j + 1] - a[i][j] - 1);//-------如有最短间距，则必然在相邻的之间
    }
    if (size > 1){//--------考虑首尾
      ans = min(ans, a[i][0] + n - a[i][size - 1] - 1);
    }
  }
  if (ans != INT_MAX)
    cout << ans << endl;
  else
   cout << -1 << endl;
}

int main() {
  int T;
  cin >> T;
  while(T--){
    solve();
  }
}
// 64 位输出请用 printf("%lld")