[Leetcode 每日精选] 1371. 每个元音包含偶数次的最长子字符串

题目样例

示例 1

输入

s = "eleetminicoworoep"

输出

13

解释

最长子字符串是 "leetminicowor" ，它包含 e，i，o 各 2 个，以及 0 个 a，u 。

示例 2

输入

"leetcodeisgreat"

输出

5

解释

最长子字符串是 "leetc" ，其中包含 2 个 e 。

题目思考

解决方案

思路

复杂度

代码

Python 3

class Solution:
    def findTheLongestSubstring(self, s: str) -> int:
        # 位运算时每个元音字母对应的下标位置, 这个顺序可以随意调换, 只要保证状态各不相同即可
        vowelindex = {'a': 0, 'e': 1, 'i': 2, 'o': 3, 'u': 4}
        # 初始化只有0状态下标是-1, 其他都标记成None代表不存在
        leftindex = [-1] + [None] * 31
        # 初始化状态为0, 因为所有元音字母都是0, 都是偶数个
        curstate = 0
        res = 0
        for i, c in enumerate(s):
            if c in vowelindex:
                # 如果当前字符是元音字母, 利用异或交换其奇偶性
                curstate ^= 1 << vowelindex[c]
            if leftindex[curstate] is None:
                leftindex[curstate] = i
            else:
                res = max(res, i - leftindex[curstate])
        return res

C++

class Solution {
public:
    int findTheLongestSubstring(string s) {
        unordered_map<char, int> vowelindex({{'a', 0},
                                             {'e', 1},
                                             {'i', 2},
                                             {'o', 3},
                                             {'u', 4}});
        vector<int> leftindex(32, INT_MIN);
        leftindex[0] = -1;
        int res = 0;

        for (int i = 0, state = 0; i < s.size(); ++i) {
            if (vowelindex.find(s[i]) != vowelindex.end()) {
                state ^= 1 << vowelindex[s[i]];
            }
            if (leftindex[state] == INT_MIN) {
                leftindex[state] = i;
            } else {
                res = max(res, i - leftindex[state]);
            }
        }

        return res;
    }
};

---

参考资料

本文分享自微信公众号 - 每日精选算法题（DailyAlgorithm）。
如有侵权，请联系 [email protected] 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。