独特字符串（Unique String）

独特字符串

题目描述

给定字符串 s 和 q 次查询，每次查询 [l, r] 区间，判断该子串是否为”独特字符串”——存在至少一个字符在该子串中恰好出现一次。

核心观察

对于每次查询 [l, r]，需要知道每个字符在该区间内出现的次数。如果存在某个字符出现恰好 1 次，则答案为 YES。

如何想到前缀和？

核心问题：区间查询 → 需要快速得到区间内字符出现次数 → 前缀和

套路总结

1. 看到区间查询：先问自己需要什么信息？
2. 这个信息可累减吗？（如次数、和）→ 可以用前缀和
3. 需要记录多种东西？ → 建多个前缀和数组

本题：26 种字符 → 26 个前缀和数组（二维前缀和）

解题思路

使用二维前缀和：

• pref[c][i]：字符 c 在 s[0:i] 中出现的次数

查询 [l, r] 时，字符 c 出现的次数为：pref[c][r] - pref[c][l-1]

枚举 26 个小写字母，检查是否存在出现次数为 1 的字符。

代码实现

n, q = map(int, input().split())
s = input().strip()

# pref[c][i]: 字符 c 在 s[0:i] 中出现的次数
pref = [[0] * (n + 1) for _ in range(26)]

for i in range(n):
    for c in range(26):
        pref[c][i + 1] = pref[c][i]
    pref[ord(s[i]) - 97][i + 1] += 1

for _ in range(q):
    l, r = map(int, input().split())
    flag = False
    for c in range(26):
        if pref[c][r] - pref[c][l - 1] == 1:
            flag = True
            break
    print("YES" if flag else "NO")

代码详解

前缀和构建

for i in range(n):
    for c in range(26):
        pref[c][i + 1] = pref[c][i]
    pref[ord(s[i]) - 97][i + 1] += 1

对于每个位置 i，先复制前面的计数，再增加当前字符的计数。

查询处理

for c in range(26):
    if pref[c][r] - pref[c][l - 1] == 1:
        flag = True
        break

计算区间 [l, r] 内每个字符的出现次数，找到恰好出现 1 次的字符即可。

复杂度分析

• 预处理：O(26 × n)
• 每次查询：O(26)
• 总时间：O(26 × n + 26 × q) ≈ O(n + q)
• 空间复杂度：O(26 × n)

优化方向

• 可以用 26 个桶分别存储每个字符的位置列表，二分查找区间内出现次数