给你一个字符串s,首尾相连成一个环形,请你在环中找出’l’,’o’,’i’字符都出现了偶数次最长子字符串的长度。
ChatGPT said:
ChatGPT
可以使用 滑动窗口 解决这个问题。首尾相连的情况可以通过将原字符串拼接一遍,即模拟环形的效果。对于这个问题,我们的目标是在这个“环”中找到 'l'
、'o'
、'i'
都出现偶数次的最长子字符串。
思路
- 滑动窗口 用来扫描字符串。我们使用两个指针
left
和right
代表当前的窗口。 - 由于字符串是首尾相连的,我们可以通过将字符串拼接成两倍长度来模拟环。
- 维护三个计数器
count_l
,count_o
,count_i
,分别记录窗口内'l'
、'o'
、'i'
的个数。 - 每次扩展
right
时,更新计数器。当窗口内'l'
、'o'
、'i'
的个数都为偶数时,尝试更新最长子串长度。 - 当计数不符合条件时,移动
left
收缩窗口。
实现代码
pythonCopy codedef longest_even_loi_substring(s: str) -> int:
n = len(s)
s = s + s # 模拟首尾相连,形成环
max_len = 0
# 记录 'l'、'o'、'i' 的出现次数
count_l, count_o, count_i = 0, 0, 0
left = 0 # 窗口的左边界
for right in range(2 * n): # 遍历整个拼接后的字符串
# 更新当前窗口中 'l'、'o'、'i' 的计数器
if s[right] == 'l':
count_l += 1
elif s[right] == 'o':
count_o += 1
elif s[right] == 'i':
count_i += 1
# 当窗口内 'l'、'o'、'i' 出现次数都是偶数时
while count_l % 2 == 0 and count_o % 2 == 0 and count_i % 2 == 0:
# 更新最大长度(窗口为 [left, right])
max_len = max(max_len, right - left + 1)
# 收缩窗口,移动左边界
if s[left] == 'l':
count_l -= 1
elif s[left] == 'o':
count_o -= 1
elif s[left] == 'i':
count_i -= 1
left += 1 # 移动左边界
# 最终返回的长度不能超过原字符串长度
return min(max_len, n)
# 示例测试
s = "loiolloi"
result = longest_even_loi_substring(s)
print(result) # 输出:8
代码详解
- 拼接字符串:
s = s + s
用来模拟首尾相连,实际上将字符串扩展成两倍长度,这样即便原字符串是环形的,滑动窗口也能完整遍历。 - 滑动窗口:
left
和right
表示滑动窗口的左右边界。我们从左到右移动right
扩展窗口,并通过调整left
来收缩窗口。
- 计数器:
- 我们维护了三个计数器
count_l
,count_o
,count_i
,用来记录窗口中'l'
、'o'
、'i'
的个数。
- 我们维护了三个计数器
- 条件检查:
- 当窗口内的
'l'
、'o'
、'i'
的个数都为偶数时,表示当前子串符合条件,尝试更新最大长度max_len
。
- 当窗口内的
- 窗口收缩:
- 当
right
移动到某个位置时,我们会根据窗口内的字符频率来调整left
,以保持'l'
、'o'
、'i'
出现次数的偶数性。
- 当
- 结果返回:
- 最终我们返回的长度不能超过原字符串的长度,因此用
min(max_len, n)
限制返回值。
- 最终我们返回的长度不能超过原字符串的长度,因此用
示例分析
对于输入字符串 "loiolloi"
,字符串首尾相连后得到 "loiolloiloiolloi"
。
- 在拼接后的字符串中,最长符合
'l'
、'o'
、'i'
都出现偶数次的子串是"loiolloi"
,长度为 8,因此结果是 8。
时间复杂度
该算法的时间复杂度是 O(n)
,其中 n
是字符串的长度,因为我们只需要遍历字符串一次。