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/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年5月19日 15:23
下一篇 2020年5月20日

相关推荐

  • leetcode380-常数时间插入、删除和获取随机元素

    原题 设计一个支持在平均 时间复杂度 O(1) 下,执行以下操作的数据结构。 insert(val):当元素 val 不存在时,向集合中插入该项。 remove(val):元素 v…

    2019年12月28日
    0100
  • 剑指offer62-圆圈中最后剩下的数字

    原题(来源Leetcode) 0,1,,n-1这n个数字排成一个圆圈,从数字0开始,每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。 例如,0、1、2、3、4这5…

    算法 2020年3月30日
    0640
  • leetcode724-寻找数组的中心索引

    原题 给定一个整数类型的数组nums,请编写一个能够返回数组“中心索引”的方法。 我们是这样定义数组中心索引的:数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。 如果数…

    算法 2019年11月13日
    0130
  • leetcode198-打家劫舍

    原题 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会…

    算法 2020年5月29日
    050
  • leetcode142-环形链表II

    原题 给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始…

    2019年12月14日
    0440
  • leetcode13-罗马数字转整数

    原题 罗马数字包含以下七种字符: I, V, X, L,C,D 和 M。 字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000 例如, 罗马数字 2…

    算法 2020年4月25日
    080
  • leetcode287-寻找重复数

    原题 给定一个包含 n + 1 个整数的数组 nums ,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。 …

    2020年1月7日
    0100
  • leetcode394-字符串解码

    原题 给定一个经过编码的字符串,返回它解码后的字符串。 编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意…

    算法 2019年12月13日
    090
  • leetcode636-函数的独占时间

    原题 给出一个非抢占单线程CPU的 n 个函数运行日志,找到函数的独占时间。 每个函数都有一个唯一的 Id,从 0 到 n-1,函数可能会递归调用或者被其他函数调用。 日志是具有以…

    算法 2020年2月2日
    0190
  • leetcode705-设计哈希集合

    原题 不使用任何内建的哈希表库设计一个哈希集合 具体地说,你的设计应该包含以下的功能 add(value):向哈希集合中插入一个值。 contains(value) :返回哈希集合…

    算法 2019年12月18日
    0140

发表回复

登录后才能评论