给你一个字符串s,首尾相连成一个环形,请你在环中找出’l’,’o’,’i’字符都出现了偶数次最长子字符串的长度。

给你一个字符串s,首尾相连成一个环形,请你在环中找出’l’,’o’,’i’字符都出现了偶数次最长子字符串的长度。

ChatGPT said:

ChatGPT

可以使用 滑动窗口 解决这个问题。首尾相连的情况可以通过将原字符串拼接一遍，即模拟环形的效果。对于这个问题，我们的目标是在这个“环”中找到 'l'、'o'、'i' 都出现偶数次的最长子字符串。

思路

1. 滑动窗口 用来扫描字符串。我们使用两个指针 left 和 right 代表当前的窗口。
2. 由于字符串是首尾相连的，我们可以通过将字符串拼接成两倍长度来模拟环。
3. 维护三个计数器 count_l，count_o，count_i，分别记录窗口内 'l'、'o'、'i' 的个数。
4. 每次扩展 right 时，更新计数器。当窗口内 'l'、'o'、'i' 的个数都为偶数时，尝试更新最长子串长度。
5. 当计数不符合条件时，移动 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

代码详解

1. 拼接字符串：s = s + s 用来模拟首尾相连，实际上将字符串扩展成两倍长度，这样即便原字符串是环形的，滑动窗口也能完整遍历。
2. 滑动窗口：
   • left 和 right 表示滑动窗口的左右边界。我们从左到右移动 right 扩展窗口，并通过调整 left 来收缩窗口。
3. 计数器：
   • 我们维护了三个计数器 count_l，count_o，count_i，用来记录窗口中 'l'、'o'、'i' 的个数。
4. 条件检查：
   • 当窗口内的 'l'、'o'、'i' 的个数都为偶数时，表示当前子串符合条件，尝试更新最大长度 max_len。
5. 窗口收缩：
   • 当 right 移动到某个位置时，我们会根据窗口内的字符频率来调整 left，以保持 'l'、'o'、'i' 出现次数的偶数性。
6. 结果返回：
   • 最终我们返回的长度不能超过原字符串的长度，因此用 min(max_len, n) 限制返回值。

示例分析

对于输入字符串 "loiolloi"，字符串首尾相连后得到 "loiolloiloiolloi"。

• 在拼接后的字符串中，最长符合 'l'、'o'、'i' 都出现偶数次的子串是 "loiolloi"，长度为 8，因此结果是 8。

时间复杂度

该算法的时间复杂度是 O(n)，其中 n 是字符串的长度，因为我们只需要遍历字符串一次。