HJ114 宝石手串

题目链接

https://www.nowcoder.com/practice/7d4d63dbe35741c8b0c40c2e2c5e7e15

题目描述

小红有一个 n 颗宝石构成的环形宝石手串，第 i 个宝石的属性为 s_i。若两个宝石的属性相同，它们会相互排斥导致断开。

小红可以摘掉一些宝石，每次摘掉后左右宝石相接依旧成环。求最少摘掉多少宝石才能使手串断开。

• 若剩余 2 颗宝石仍无法断开，输出 -1

解题思路

核心思想：在环形字符串中，找两个相同字符之间的最小距离

1. 环形模拟：将字符串 s 拼接为 s+s，模拟环形结构
2. 一次遍历：用哈希表记录每个字符上次出现的位置
3. 计算距离：当遇到重复字符时，i - pos[char] - 1 即为两字符间的距离
4. 答案：最小距离 - 1（中间隔着多少颗宝石需要摘掉）

代码实现

tt = int(input())
for _ in range(tt):
    n = int(input())
    s = input().strip()

    # 特殊情况：2个不同宝石无法断开
    if n == 2 and s[0] != s[1]:
        print(-1)
        continue

    s2 = s + s  # 拼接模拟环形
    pos = {}
    ans = n - 1  # 最大可能距离

    for i, j in enumerate(s2):
        if j in pos:
            ans = min(ans, i - pos[j] - 1)
        pos[j] = i

    # 所有字符都不同，无法断开
    if ans == n - 1:
        print(-1)
    else:
        print(ans)

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)

示例解析

输入	输出	解释
2 / ac	-1	两个宝石不同，无法断开
3 / aac	0	两个 ‘a’ 相邻，距离为1，摘0个即可断开