题解 | 宝石手串

def cut_bracelet(s: str, n: int) -> int:
    if len(set(s)) == n:  # 当没有重复字符时候，相当于无法断裂
        return -1
    if s[0] == s[n - 1]:  # 当珠串首尾相连的字符相同
        return 0
    s_dict = {}  # 用于统计每个字符的位置
    for i, ss in enumerate(s):
        if ss not in s_dict.keys():  # 如果之前没有统计过该字符
            s_dict[ss] = [i]
        else:  # 如果之前统计过该字符，将该字符的位置添加进去
            s_dict[ss].append(i)
    min_cut_num = n - 1  # 设置摘除数量
    for key, value in s_dict.items():  # key为字符，value为字符的位置
        if len(value) > 1:  # 因为只有宝石数量大于1的时候，才能断裂，所以数量为1的宝石可以不管
            # [value[i + 1] - value[i] - 1 for i in range(len(value) - 1)]用于统计字符相邻之间的摘除数量
            # [n - (value[-1] - value[0]) - 1]是从value[-1]后面的位置，value[0]前面的位置摘除时需要摘除的数量
            temp_min_distance = min([value[i + 1] - value[i] - 1
                                     for i in range(len(value) - 1)] + [n - (value[-1] - value[0]) - 1])
            if temp_min_distance < min_cut_num:  # 当计算的最少摘除数量小于min_cut_num时，更新min_cut_num
                min_cut_num = temp_min_distance
                if min_cut_num == 0:  # 之前已经判断了无法破坏的情况，当如果提前遇到两个相邻的相同字符，结束并输出0
                    return 0
    return min_cut_num


while True:
    try:
        n = int(input())  # 代表数据组数
        res = []
        for _ in range(n):
            n1 = int(input())  # 代表手串初始的宝石数量
            s = input()
            res.append(cut_bracelet(s, n1))
        print(*res, sep="\n")

    except:
        break