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

彭晨涛 • 2020年5月20日 13:53 • 算法 • 阅读 141

原题

给你一个字符串 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/

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

原题

解法

思想

代码

相关推荐

发表回复