- About
- Contact Us
- Privacy
- Terms of Service
- Copyright Complaint
- Language
- Legacy mode
- Theme
- 京ICP备2025123107号-1
- Worker 0, 208ms
- Powered by Hydro v4.18.0 Community
给定一个字符串 s，要求找到其中一个最短的子串，使得该子串包含了所有的小写字母（a 至 z）。如果不存在这样的子串，返回 -1。
请注意，字符串中的字母不需要按顺序排列，且可能包含重复字母。
s，长度 n，满足 1≤n≤105。-1。ykjygvedtysvyymzfizzwkjamefxjnrnphqwnfhrnbhwjhqcgqnplodeestu
49
aabccabc
-1
给定一个字符串 s，要求找到其中一个最短的子串，使得该子串包含了所有的小写字母（a 至 z）。如果不存在这样的子串，返回 -1。
请注意，字符串中的字母不需要按顺序排列，且可能包含重复字母。
我们可以使用滑动窗口来解决这个问题。滑动窗口的核心思想是固定一端（例如左端），而枚举另一端（例如右端）。我们通过不断扩展窗口右端来增加包含的字符，当窗口内包含所有小写字母时，尝试收缩左端以找到最短的子串。
初始化变量：
left 和 right 来表示当前滑动窗口的左右边界，初始都指向字符串的起始位置。count 来记录窗口内各个小写字母的出现次数，索引对应字母 a 到 z。unique 来记录当前窗口内包含的不同小写字母的数量。min_len 来记录满足条件的最短子串的长度，初始值设为字符串的长度加一。滑动窗口扩展：
滑动窗口收缩：
unique 等于 26 时，表示当前窗口包含了所有的小写字母。更新最小长度：
min_len。结果判断：
min_len 仍为初始值，说明字符串中不存在包含所有26个小写字母的子串，返回 -1。def shortest_all_letters_substring(s):
# 记录每个字母出现的次数
count = [0] * 26
unique = 0 # 当前窗口中不同字母的数量
n = len(s)
min_len = n + 1 # 初始值设置为大于可能的最大长度
left = 0
for right in range(n):
c = s[right]
if 'a' <= c <= 'z': # 仅处理小写字母
idx = ord(c) - ord('a')
if count[idx] == 0:
unique += 1 # 新增一个不同的字母
count[idx] += 1
# 当窗口包含所有26个字母时，尝试收缩左边界
while unique == 26:
# 更新最小长度
min_len = min(min_len, right - left + 1)
cl = s[left]
if 'a' <= cl <= 'z':
idx = ord(cl) - ord('a')
count[idx] -= 1
if count[idx] == 0:
unique -= 1 # 如果移出的是唯一的字母，unique减少
left += 1 # 收缩窗口
return min_len if min_len <= n else -1 # 如果找到了符合条件的子串，返回最小长度，否则返回 -1
# 读取输入字符串并调用函数
if __name__ == '__main__':
s = input().strip()
print(shortest_all_letters_substring(s))