当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.1371.Find the Longest Substring Containing Vowels in Even Counts 每个元音包含偶数次的最长子字符串

LeetCode.1371.Find the Longest Substring Containing Vowels in Even Counts 每个元音包含偶数次的最长子字符串

题目描述

1371 Find the Longest Substring Containing Vowels in Even Counts
https://leetcode-cn.com/problems/find-the-longest-substring-containing-vowels-in-even-counts/

给你一个字符串 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.1248.Count Number of Nice Subarrays 统计优美子数组
LeetCode.560.Subarray Sum Equals K 和为K的子数组


解题过程

对每个位置 i,计算以 i 为结尾的满足条件的最长子串的长度,其实就是找一个最小的下标 j(0<=j<=i) 使得子数组 [j,i] 中每个元音字母都是偶数。

private static class SolutionV202005 {
    public int findTheLongestSubstring(String s) {
        if (null == s || s.length() < 1) {
            return 0;
        }
        // a,e,i,o,u 的奇偶状态,低 5 位分别表示每个元音的奇偶状态,第 0 位表示 a 的奇偶状态,依次类推,0 表示偶, 1表示奇
        int status = 0;
        // 每个奇偶状态的最小下标
        Map<Integer, Integer> map = new HashMap<>();
        // 先放入一个 a,e,i,o,u 全为0的状态,下标为 -1
        map.put(0, -1);
        int maxLength = 0;
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == 'a') {
                status ^= 1;
            } else if (chars[i] == 'e') {
                status ^= (1 << 1);
            } else if (chars[i] == 'i') {
                status ^= (1 << 2);
            } else if (chars[i] == 'o') {
                status ^= (1 << 3);
            } else if (chars[i] == 'u') {
                status ^= (1 << 4);
            }
            if (map.containsKey(status)) {
                // 遇到奇偶状态相同的,则当前位置到此状态的最小下标之间的子数组满足条件(每个元音包含偶数次)
                maxLength = Math.max(maxLength, i - map.get(status));
            } else {
                // 放入此状态的最小下标
                map.put(status, i);
            }
        }
        return maxLength;
    }
}

GitHub代码

algorithms/leetcode/leetcode/_1371_LongestSubstringContainingEvenVowels.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_1371_LongestSubstringContainingEvenVowels.java


上一篇 LeetCode.105.Construct Binary Tree from Preorder and Inorder Traversal 从前序与中序遍历序列构造二叉树

下一篇 LeetCode.680.Valid Palindrome II 验证回文字符串 Ⅱ

阅读
评论
558
阅读预计3分钟
创建日期 2020-05-20
修改日期 2020-05-20
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论