LeetCode-1371-每个元音包含偶数次的最长子字符串
Miyagi Lv1
 2021-02-14 14:59:48      801 字  3 分钟  

题目地址（LeetCode-1371）

https://leetcode.com/problems/find-the-longest-substring-containing-vowels-in-even-counts/

题目描述

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

示例1:

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

示例2:

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

示例3:

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

解法

  • a,e,i,o,u 五个字母可以分别用二进制上一的一位来表示其在字符串中出现次数的奇偶，第0位上0表示字母a出现了偶数次，1表示出现了奇数次；第1位上0表示字母e出现了偶数次，1表示出现了奇数次，以此类推。则二进制数00000对应了a,e,i,o,u各个字母出现奇偶次的32种可能排列组合。

  • 对于每一个子字符串来说，[0,i]都会对应了一个五位二进制数xxxxx，只有当该数为00000时，该子字符串才是题目所需的答案。对于子字符串[0,i]和[0,j]来说，当这两个子字符串所对应的二进制数相同时，则二者之间的[i+1,j]子字符串所对应的二进制状态数一定是00000，即满足题目所需。

    按照上述思路，代码如下：

    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
    class Solution {
        public int findTheLongestSubstring(String s) {
            HashMap<Character, Integer> hashMap = new HashMap<Character, Integer>();
            HashMap<Integer, Integer> stateMap = new HashMap<Integer, Integer>();
            hashMap.put('a', 1);
            hashMap.put('e', 2);
            hashMap.put('i', 4);
            hashMap.put('o', 8);
            hashMap.put('u', 16);
            int res = 0;
            int max = 0;
            stateMap.putIfAbsent(0, -1);
            for (int i = 0; i < s.length(); i++) {
                if (hashMap.containsKey(s.charAt(i))) {
                    res ^= hashMap.get(s.charAt(i));
                }
                // 如果当前二进制状态在之前出现过，则计算二者之间的子字符串有多长，该子字符串一定是满足题目要求的子字符串
                if (stateMap.containsKey(res)){
                    max = Math.max(max, i - stateMap.get(res));
                }
                // 记录每个二进制状态第一次出现时的索引
                stateMap.putIfAbsent(res, i);
            }
            return max;
        }
    }

    Runtime beats: 32.38%
    Memory usage beats: 45.71%

以示例1中的测试用例为例，下表罗列了各个从索引0开始的子字符串对应的二进制状态码：

子字符串 二进制状态码 索引位置
e 00010 0
el 00010 1
ele 00000 2
elee 00010 3
eleet 00010 4
eleetm 00010 5
eleetmi 00110 6
eleetmin 00110 7
eleetmini 00010 8
eleetminic 00010 9
eleetminico 01010 10
eleetminicow 01010 11
eleetminicowo 00010 12
eleetminicowor 00010 13
eleetminicoworo 01010 14
eleetminicoworoe 01000 15
eleetminicoworoep 01000 16

其中子字符串e和eleetminicowor所对应的二进制状态码一样，二者相减得13，即字符串leetminicowor为符合要求的子字符串。

 评论