Medium

题目描述

给你一个字符串 s，请你返回满足以下条件的最长子字符串的长度：每个元音字母（‘a’, ’e’, ‘i’, ‘o’, ‘u’）在子字符串中都出现偶数次。

示例 1:

输入: s = "eleetminicoworoep"
输出: 13
解释: 最长子字符串是 "leetminicowor"，它包含 e, i, o 各 2 个，a, u 各 0 个。

示例 2:

输入: s = "leetcodeisgreat"
输出: 5
解释: 最长子字符串是 "leetc"，它包含 2 个 e。

示例 3:

输入: s = "bcbcbc"
输出: 6
解释: 在这种情况下，给定的字符串 "bcbcbc" 就是最长的，因为所有元音 a, e, i, o, u 都出现 0 次。

约束条件:

  • 1 <= s.length <= 5 x 10^5
  • s 只包含小写英文字母。

提示:

  • 用位掩码表示元音字母的奇偶性
  • 预计算元音字母位掩码的前缀异或，然后获取最长有效子字符串

解题思路

这道题的核心思路是使用状态压缩和前缀异或的技巧。

关键观察：

  1. 我们只关心每个元音字母出现的次数是奇数还是偶数，而不是具体次数
  2. 可以用一个5位的二进制数（位掩码）来表示5个元音字母的奇偶状态
  3. 当两个位置的状态相同时，它们之间的子字符串中所有元音都出现偶数次

算法步骤：

  1. 使用位掩码 state 记录当前位置各元音字母的奇偶性，初始为0（全为偶数）
  2. 遍历字符串，遇到元音字母就将对应位翻转（异或操作）
  3. 使用哈希表记录每个状态第一次出现的位置
  4. 当遇到相同状态时，计算当前位置与该状态第一次出现位置之间的距离
  5. 维护最长距离作为答案

为什么这样有效？ 如果位置 i 和位置 j 的状态相同，说明从 i+1 到 j 这段区间内，每个元音字母出现的次数都是偶数次（因为相同状态被"抵消"了）。

时间复杂度：O(n)，空间复杂度：O(1)（因为状态数最多32种）

代码实现

class Solution {
public:
    int findTheLongestSubstring(string s) {
        unordered_map<int, int> stateMap;
        stateMap[0] = -1; // 初始状态，所有元音都是偶数次
        
        int state = 0;
        int maxLen = 0;
        
        for (int i = 0; i < s.length(); i++) {
            char c = s[i];
            // 更新状态
            if (c == 'a') state ^= 1;
            else if (c == 'e') state ^= 2;
            else if (c == 'i') state ^= 4;
            else if (c == 'o') state ^= 8;
            else if (c == 'u') state ^= 16;
            
            if (stateMap.count(state)) {
                maxLen = max(maxLen, i - stateMap[state]);
            } else {
                stateMap[state] = i;
            }
        }
        
        return maxLen;
    }
};

class Solution:
    def findTheLongestSubstring(self, s: str) -> int:
        state_map = {0: -1}  # 初始状态，所有元音都是偶数次
        vowels = {'a': 1, 'e': 2, 'i': 4, 'o': 8, 'u': 16}
        
        state = 0
        max_len = 0
        
        for i, c in enumerate(s):
            if c in vowels:
                state ^= vowels[c]
            
            if state in state_map:
                max_len = max(max_len, i - state_map[state])
            else:
                state_map[state] = i
                
        return max_len

public class Solution {
    public int FindTheLongestSubstring(string s) {
        Dictionary<int, int> stateMap = new Dictionary<int, int>();
        stateMap[0] = -1; // 初始状态，所有元音都是偶数次
        
        int state = 0;
        int maxLen = 0;
        
        for (int i = 0; i < s.Length; i++) {
            char c = s[i];
            // 更新状态
            switch (c) {
                case 'a': state ^= 1; break;
                case 'e': state ^= 2; break;
                case 'i': state ^= 4; break;
                case 'o': state ^= 8; break;
                case 'u': state ^= 16; break;
            }
            
            if (stateMap.ContainsKey(state)) {
                maxLen = Math.Max(maxLen, i - stateMap[state]);
            } else {
                stateMap[state] = i;
            }
        }
        
        return maxLen;
    }
}

var findTheLongestSubstring = function(s) {
    const stateMap = new Map();
    stateMap.set(0, -1); // 初始状态，所有元音都是偶数次
    
    const vowels = new Map([['a', 1], ['e', 2], ['i', 4], ['o', 8], ['u', 16]]);
    
    let state = 0;
    let maxLen = 0;
    
    for (let i = 0; i < s.length; i++) {
        const c = s[i];
        if (vowels.has(c)) {
            state ^= vowels.get(c);
        }
        
        if (stateMap.has(state)) {
            maxLen = Math.max(maxLen, i - stateMap.get(state));
        } else {
            stateMap.set(state, i);
        }
    }
    
    return maxLen;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历字符串一次，每次操作都是常数时间
空间复杂度O(1)哈希表最多存储32种不同状态（2^5），为常数空间