题解 | 宝石手串

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        if(!in.hasNextInt()) return;

        int t = in.nextInt();
        while (t-- > 0) {
            int n = in.nextInt();
            String s = in.next();
            System.out.println(solve(n, s));
        }
    }

    public static int solve(int n, String s) {
        // 1.检查是否已经满足断开
        for(int i = 0; i < n; i++) {
            if(s.charAt(i) == s.charAt((i+1) % n)) {
                return 0;
            }
        }

        // 2.如果 n 为 2 且不满足断开条件，返回 -1
        if(n == 2) return -1;
        
        int minOps = n; // 初始化为 n
        // 记录每个字符最后一次出现的位置
        int[] lastPos = new int[26];
        Arrays.fill(lastPos, -1);

        // 3.线性扫描寻找最近的相同字符对
        for(int i = 0; i < n; i++) {
            int charIdx = s.charAt(i) - 'a';
            if(lastPos[charIdx] != -1) {
                // 计算两个相同字符的间距
                int dist = i - lastPos[charIdx] - 1;
                minOps = Math.min(minOps, dist);
            }
            lastPos[charIdx] = i;
        }

        // 4.考虑环形跨端情况（比如 a...(middle)...a）
        // 记录字符第一次出现的位置
        int[] firstPos = new int[26];
        Arrays.fill(firstPos, -1);
        for(int i = 0; i < n; i++) {
            int charIdx = s.charAt(i) - 'a';
            if(firstPos[charIdx] == -1) {
                firstPos[charIdx] = i;
            }
        }
        for(int i = 0; i < 26; i++) {
            if(firstPos[i] != -1 && lastPos[i] != -1 
            && firstPos[i] != lastPos[i]) {
                // 跨越首尾的距离：首部到 firstPos 的距离 + 尾部到 lastPost 的距离
                int dist = firstPos[i] + (n - 1 - lastPos[i]);
                minOps = Math.min(minOps, dist);
            }
        }

        // 5.结果校验
        if(minOps == n) return -1; // 没有任何相同宝石

        // 特殊条件：摘掉宝石后，剩余宝石数量必须大于 2 才能视为破坏成功
        // 如果 n - minOps <= 2，说明剩下的宝石只有 2 颗或更少
        if(n - minOps <= 2) return -1;
        return minOps;
    }
}