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

Leecode-1371-Find the Longest Substring Containing Vowels in Even Counts

思路：前缀和+位运算

题目描述

给你一个字符串 s ，请你返回满足以下条件的最长子字符串的长度：

• 每个元音字母，即 ‘a’，’e’，’i’，’o’，’u’ ，在子字符串中都恰好出现了偶数次。

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

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

输入：s = "bcbcbc"
输出：6
解释：这个示例中，字符串 "bcbcbc" 本身就是最长的，因为所有的元音 a，e，i，o，u 都出现了 0 次。

Solution：

1. 二进制用来压缩状态

aeiou 分别对应二进制 
00001，00010，00100，01000，10000
其中 0 表示对应元音出现了偶数次数，1 表示奇数


那么问题来了？为什么我们要这么搞？
答：因为这样可以用到位运算，在二进制中，1^0 = 1 ,0^0 = 0(那么当出现偶数次的话对应位就是0，奇数次对应位就是1)

所以由这个规律可以断定，当一个状态重复出现的时候，一定出现了偶数次，举例如下：

31-->30-->28-->29-->31

对应的二进制位 [11111]-->[11110]-->[11100]-->[11101]-->[11111]

一个合理的字符串变化：
aeiou --> aeioua -->aeiouae-->aeiouaea-->aeiouaeae

由此可见，从 aeiou 到 aeiouaeae 这个过程中，多余出来的 aeae 为符合条件的字符串。

所以在这个过程中，不管中间发生了什么变化，这两个状态之间对应的元音为偶数，也就是一定符合题目的字符串。

Java

Solution :

class Solution {
    public int findTheLongestSubstring(String s) {
        Map<Integer, Integer> map = new HashMap<>();

        int state  = 0;
        int maxlen = 0;

        // 初始化
        // 为了计算长度方便定义，
        // 或者理解为，
        // 开始计算前，参照点在第一个字符之前，也就是 -1 的位置
        map.put(0,-1);

        // a e i o u 分别在第12345个bit，来表示出现次数的奇偶性
        for (int i = 0; i < s.length(); i++) {
            // 遍历每个索引位置，是元音进行异或运算
            if (s.charAt(i) == 'a'){
                state ^= 1<<0;  // 1
            }

            if (s.charAt(i) == 'e'){
                state ^= 1<<1;  // 2
            }

            if (s.charAt(i) == 'i'){
                state ^= 1<<2;  // 4
            }

            if (s.charAt(i) == 'o'){
                state ^= 1<<3;  // 8
            }

            if (s.charAt(i) == 'u'){
                state ^= 1<<4;  // 16
            }

            // 对状态进行判断，如果这个状态之前出现过（说明出现了偶数次）(辅音或者重复的元音都要计算长度)
            // 更新最大长度即可
            if (map.containsKey(state)){
                maxlen = Math.max(maxlen,i - map.get(state));
            }else {
                // 如果当前的 state 没有出现过，
                // 那么以这个 state 为键，记录下当前位置，也就是索引的位置
                map.put(state,i);
            }

        }
        return maxlen;
    }
}

测试用例：

public static void main(String[] args) {
    Solution solution = new Solution();
    System.out.println(solution.findTheLongestSubstring("leetcodeo"));
}

• 时间复杂度：其中 n 为字符串 s 的长度。我们只需要遍历一遍字符串即可求得答案，因此时间复杂度为 O(n)。
• 空间复杂度：O(S) S = 32 ，用来存储状态的集合长度

Python

Solution :

打赏