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

原题

给你一个字符串 s ,请你返回满足以下条件的最长子字符串的长度:每个元音字母,即 'a','e','i','o','u' ,在子字符串中都恰好出现了偶数次。

示例 1:

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

示例 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 只包含小写英文字母。

解法

思想

使用官方题解的前缀和+状态压缩!

这道题不好想,如果用暴力在leetcode绝对超时,可以想到用前缀和的方法。

前缀和怎么做呢?如果要两个字符串的差值(字符串交集)中,a,e,i,o,u全部为偶数,那么根据数学知识,偶数减偶数是偶数,奇数减奇数也是偶数。也就是说两个字符串中的这五个字母出现的奇偶性必须一样!

而五个字母,每个字母出现的次数都可奇可偶,组合出来的情况有很多种,在遍历的时候遇到其中一种奇偶性组合,如何知道最早出现的同一种奇偶性组合出现在哪个位置呢?

这里有一种方法:遍历的时候记录并计算所有字母的个数,然后对每次遍历到的位置,将它的奇偶性组合编码成字符串,例如“奇偶奇偶奇”,代表a,i,u出现奇数个,而e,o出现偶数个。然后就以这个字符串为键,第一次出现的顺序为值存放到哈希表中。后面只要出现相同的奇偶性排列,就把它从哈希表中取出来,就知道最早出现的位置,两个位置一减就是字符串的长度。

但是这种方法需要构造字符串,并且需要记录五种字母出现的个数,十分麻烦,那么可以利用“状态压缩”+“位运算”的方法:将这种奇偶性排列编码成一个五位的二进制位串,例如二进制的"10101",代表a,i,u出现奇数个,而e,o出现偶数个。每一个字母都映射到位串的一个位上,而再出现一个字母的时候,就通过异或运算更改对应位上的值。

例如: "10101" :a,i,u出现奇数个,e,o出现偶数个
(再出现一个i)->"10101"^"100" = "10001",即a,u出现奇数个,e,i,o出现偶数个。

代码

class Solution {
    public int findTheLongestSubstring(String s) {
        int n = s.length();
        int[] pos = new int[1 << 5];
        // 如果是-1,说明还没有出现这种奇偶性排列
        Arrays.fill(pos, -1);
        int ans = 0, status = 0;
        //第一个全偶的情况出现在还没开始遍历的时候
        pos[0] = 0;
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if (ch == 'a') {
                status ^= (1 << 0);
            } else if (ch == 'e') {
                status ^= (1 << 1);
            } else if (ch == 'i') {
                status ^= (1 << 2);
            } else if (ch == 'o') {
                status ^= (1 << 3);
            } else if (ch == 'u') {
                status ^= (1 << 4);
            }
            if (pos[status] >= 0) {
                ans = Math.max(ans, i + 1 - pos[status]);
            } else {
                pos[status] = i + 1;
            }
        }
        return ans;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode1371-%e6%af%8f%e4%b8%aa%e5%85%83%e9%9f%b3%e5%8c%85%e5%90%ab%e5%81%b6%e6%95%b0%e6%ac%a1%e7%9a%84%e6%9c%80%e9%95%bf%e5%ad%90%e5%ad%97%e7%ac%a6%e4%b8%b2/