讨论/题目交流/🐱 第 21 场夜喵双周赛/
🐱 第 21 场夜喵双周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

4 分 - 上升下降字符串
4 分 - 每个元音包含偶数次的最长子字符串
5 分 - 二叉树中的最长交错路径
6 分 - 二叉搜索子树的最大键值和

展开讨论

关于第二题的 O(N)O(N) 解法:

class Solution:
    def findTheLongestSubstring(self, s: str) -> int:
        keys = ['a', 'e', 'i', 'o', 'u']
        count = { k: 0 for k in keys }

        state = {}
        for i in range(32):
            k = ''.join(str(i >> j & 1) for j in range(5))
            state[k] = -1

        ret = 0
        for i in range(len(s)):
            if s[i] in count: count[s[i]] += 1
            key = ''.join([str(count[k] % 2) for k in keys])
            if key == '00000': ret = max(ret, i + 1)
            elif state[key] < 0: state[key] = i
            else: ret = max(ret, i - state[key])
        return ret

遍历字符串 SS 中的每一个字符,同时统计已遍历部分各个元音字母的数目,那么 a, e, i, o, u 五个字母的奇偶性,可以组成 32 个状态,当五个字符全为偶数时,证明已遍历的字符数就是最大长度;当五个字符中存在奇数个时,只需要根据状态键,找到第一次变成该状态时的索引即可,然后记录最大长度,就能得到最终解。

类似题目:第 20 场双周赛第三题:1358. 包含所有三种字符的子字符串数目

以后遇到这种 substring 长度最大化的题目,都按照这种套路解就行了。

2
展开全部 21 讨论