题解 | 宝石手串

import java.util.Scanner;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        while (T-- > 0) {
            int n = in.nextInt();
            String s = in.next();
            boolean hasAdjacent = false;
            for (int i = 0; i < n; i++) {
                int next = (i + 1) % n;
                if (s.charAt(i) == s.charAt(next)) {
                    hasAdjacent = true;
                    break;
                }
            }
            if (hasAdjacent) {
                System.out.println(0);
                continue;
            }
            boolean allUnique = true;
            int[] count = new int[26];
            for (char c : s.toCharArray()) {
                if (++count[c - 'a'] > 1) {
                    allUnique = false;
                }
            }
            if (allUnique) {
                System.out.println(-1);
                continue;
            }
            ArrayList<Integer>[] pos = new ArrayList[26];
            for (int i = 0; i < 26; i++) {
                pos[i] = new ArrayList<>();
            }
            for (int i = 0; i < n; i++) {
                char c = s.charAt(i);
                pos[c - 'a'].add(i);
            }
            int minGap = Integer.MAX_VALUE;
            for (int c = 0; c < 26; c++) {
                ArrayList<Integer> list = pos[c];
                if (list.size() < 2) {
                    continue;
                }
                int m = list.size();
                for (int i = 0; i < m; i++) {
                    int current = list.get(i);
                    int nextPos = list.get((i + 1) % m);
                    int diff = Math.abs(nextPos - current);
                    int gap = Math.min(diff, n - diff);
                    if (gap < minGap) {
                        minGap = gap;
                    }
                }
            }
            System.out.println(minGap - 1);
        }
    }
}

https://www.nowcoder.com/discuss/727521113110073344

思路：

1. 输入处理：读取输入的测试用例数量，并处理每个测试用例。
2. 检查相邻宝石：遍历每个宝石及其下一个宝石（考虑环形），检查是否存在相邻相同的属性。
3. 检查所有唯一属性：统计每个属性的出现次数，若所有属性均唯一，则直接返回-1。
4. 记录位置：为每个属性记录其在字符串中的位置。
5. 计算最小间隔：对于每个重复属性，计算其所有位置之间的最小间隔，并更新全局最小间隔。
6. 输出结果：最小间隔减一即为需要摘掉的最少宝石数。