本文介绍一种 o(n) 时间复杂度的高效解法：通过寻找“循环意义上”能覆盖字符串一端的最长无重复字符子串，用总长减去其长度，即得需删除的最短子串长度。
本文介绍一种 o(n) 时间复杂度的高效解法：通过寻找“循环意义上”能覆盖字符串一端的最长无重复字符子串，用总长减去其长度，即得需删除的最短子串长度。
该问题本质是：删除一个连续子串后，剩余字符（保持原顺序）全部互不相同。注意——剩余部分由首段前缀 + 尾段后缀拼接而成（即删除的是中间一段），因此合法结果等价于存在某个分割点 i ≤ j，使得 s[0:i] + s[j:n] 中无重复字符。
关键洞察在于：若将字符串视为“可循环拼接”的结构（即允许跨结尾与开头连续取字符），那么所有合法的、由前缀+后缀构成的无重复字符序列，恰好对应一个在循环字符串中、长度不超过 n、且至少一端触达原始字符串边界（索引 0 或 n−1）的无重复字符连续子串。
基于此，算法核心步骤如下：
- 枚举每个可能的起始位置 startPos（0 到 n−1）；
- 从该位置开始，在循环索引下（(startPos + k) % n）尽可能向右扩展，维护一个 set 记录已出现字符；
- 一旦遇到重复字符，停止扩展；此时当前循环子串长度为 curlen；
- 仅当该子串“触及原始字符串一端”（即 startPos == 0，或子串覆盖到末尾：startPos + curlen >= n），才更新全局最大长度 maxlen；
- 回溯：移除 s[startPos]，收缩窗口，继续尝试下一位置。
最终答案即 n - maxlen。
以下是优化后的完整实现（含边界处理与清晰注释）：
def findShortestSubstring(s):
n = len(s)
if n < 2:
return 0
chars = set()
maxlen = 0
curlen = 0
# 枚举每个起始位置
for start in range(n):
# 从 start 开始，在循环索引下扩展无重复子串
while curlen < n and s[(start + curlen) % n] not in chars:
chars.add(s[(start + curlen) % n])
curlen += 1
# 检查该子串是否“触达原始字符串边界”
# 即：从位置 0 开始，或延伸至末尾（覆盖 s[n-1]）
if start == 0 or start + curlen >= n:
maxlen = max(maxlen, curlen)
# 回溯：移除起始字符，为下一轮准备
chars.remove(s[start])
curlen -= 1
return n - maxlen✅ 正确性保障：
- 所有合法的 prefix + suffix 组合，在循环视角下必为某一起点出发的连续无重复段，且因 prefix 在前、suffix 在后，该段必然跨越原始串末尾或始于开头；
- 枚举覆盖全部可能性，maxlen 即保留最多字符的合法方案。
⚠️ 注意事项：
- 原始提问中滑动窗口思路（针对重复字符集合做最小覆盖）本质上解决的是「覆盖所有重复字符的最短子串」，但本题目标不同：删除后剩余部分需全局唯一，而非仅消除重复——二者不可等价转换；
- 循环索引 (start + curlen) % n 是关键技巧，避免显式拼接 s + s，节省空间；
- 时间复杂度为 O(n)：每个字符至多被加入/移出 chars 集合一次；
- 空串或单字符返回 0，符合题意（无需删除）。
测试验证（部分）：
assert findShortestSubstring("aabbcc") == 4 # 删除 "aabb" 或 "bbcc" → "ac" 或 "ab" 等
assert findShortestSubstring("abba") == 2 # 删除 "bb" → "aa"? 不合法；实际删 "bb" 得 "aa" 仍重复 → 正确解为删 "ab" 或 "ba"，剩 "ab"/"ba" → 长度 2
assert findShortestSubstring("abcd") == 0 # 已全唯一该解法兼顾效率与思想深度，是典型“转化问题视角”类算法的优秀范例。
