长大后想做什么？做回小孩！

0%

LeetCode——每个元音包含偶数次的最长子字符串

发表于 分类于 Valine：
本文字数： 520

NO.1371 每个元音包含偶数次的最长子字符串 中等

Yo88u8.png

暴力解法，枚举每个子串，然后遍历子串记录其中元音字母的出现情况，记录符合要求的最长子串，O(n^3)超时。

然后看见子串，就想到了滑动窗口，滑了半天也没滑出来结果。

看别人的题解，时刻提醒这自己勤能补拙！

思路一：动态规划+状态压缩 直接说结果，用五个二进制位来分别表示 aeiou 的出现次数，出现偶数次对应位是 0，计数次对应位是 1，所以这个表示范围是 00000~11111 ，即十进制的 0~31 共 32 种状态 status。

因此状态数组 dp[status] 表示出现当前状态的子串的结尾下标，例如：

status 是二进制的 01010 表示 eo 出现计数次、aiu 出现偶数次，此时的 status=10 如果 dp[status]=8 ，表示出现当前状态的子串的结尾下标是 8 ，下次再出现同样的状态时用 当前下标 i - dp[status] +1 即可得到第 i 元素作为结尾符合要求的最长子串。

综上所述 dp[status] 数组的含义是：status 状态子串的结尾下标。

初始化：dp[0] = 0 即空串的状态为 00000，其余都填充为 -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
public int findTheLongestSubstring(String s) {
    int[] dp = new int[32];
    //初始化
    Arrays.fill(dp, -1);
    dp[0] = 0;
    int status = 0;
    int ans = 0;
    //遍历
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        //记录元音字母出现的次数,更新状态
        if (c == 'a') {
            status ^= (1 << 0);
        } else if (c == 'e') {
            status ^= (1 << 1);
        } else if (c == 'i') {
            status ^= (1 << 2);
        } else if (c == 'o') {
            status ^= (1 << 3);
        } else if (c == 'u') {
            status ^= (1 << 4);
        }
        //如果状态重复出现
        if (dp[status] >= 0) {
            ans = Math.max(ans, i - dp[status] + 1);
        } else {
            dp[status] = i + 1;
        }
    }
    return ans;
}

时间复杂度：O(n)

空间复杂度：O(1)

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github