最长元音偶数子串问题

在这里插入图片描述

求解思路

这道题我们不需要记录每个元音的具体出现次数，只需要关心它们的奇偶性。

用一个5位的二进制数表示5个元音的奇偶状态，第0-4位分别对应a、e、i、o、u，0表示偶数次，1表示奇数次。

遍历字符串时，遇到元音就通过异或操作翻转对应位，这样当前状态就表示从开头到当前位置各元音的奇偶性。

如果某个状态之前出现过，说明这两个位置之间的子串中所有元音都出现了偶数次（因为奇偶性相同），此时计算长度并更新答案。

用哈希表记录每个状态最早出现的位置，这样就能找到最长的满足条件的子串。

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


public static int findTheLongestSubstring(String s) {
    int n = s.length();
    // 状态数组，32种可能的奇偶组合(2^5)
    int[] map = new int[32];
    Arrays.fill(map, -2);  // -2表示未出现
    map[0] = -1;  // 初始状态（全偶数）在-1位置
    
    int ans = 0;
    for (int i = 0, status = 0, m; i < n; i++) {
        m = move(s.charAt(i));
        if (m != -1) {
            // 翻转对应元音的奇偶位
            status ^= 1 << m;
        }
        
        if (map[status] != -2) {
            // 相同状态之前出现过，计算子串长度
            ans = Math.max(ans, i - map[status]);
        } else {
            // 记录该状态首次出现位置
            map[status] = i;
        }
    }
    return ans;
}

public static int move(char cha) {
    switch (cha) {
        case 'a': return 0;
        case 'e': return 1;
        case 'i': return 2;
        case 'o': return 3;
        case 'u': return 4;
        default: return -1;
    }
}

如果觉得有帮助，欢迎点赞、关注、转发~