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日

相关推荐

  • leetcode199-二叉树的右视图

    原题 给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。 示例: 输入: [1,2,3,null,5,null,4] 输出:&nb…

    算法 2020年4月22日
    0110
  • leetcode1013-将数组分成和相等的三个部分

    原题 给你一个整数数组 A,只有可以将其划分为三个和相等的非空部分时才返回 true,否则返回 false。 形式上,如果可以找出索引 i+1 < j 且满足 (A[0] +…

    算法 2020年3月11日
    0560
  • leetcode203-移除链表元素

    原题 删除链表中等于给定值 val 的所有节点。 示例: 输入: 1->2->6->3->4->5->6, val = 6 输出: 1->2->3->4->5 解法 思想 pre指…

    算法 2019年12月16日
    0360
  • leetcode200-岛屿数量

    原题 给定一个由 '1'(陆地)和 '0'(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水…

    算法 2019年11月24日
    0150
  • leetcode392-判断子序列

    原题 https://leetcode.cn/problems/is-subsequence/description 解法 最简单的双指针略。 对于进阶场景:如果有大量输入的 S,…

    算法 2024年3月24日
    030
  • leetcode66-加一

    原题 给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。 最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。 你可以假设除了整数 0 之外,这个整数不会以…

    算法 2019年11月14日
    0140
  • leetcode63-不同路径II

    原题 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Fi…

    2020年2月22日
    0130
  • leetcode410-分割数组的最大值

    原题 给定一个非负整数数组和一个整数 m,你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。 注意:数组长度 n 满足以下条件: 1…

    算法 2020年1月9日
    0640
  • leetcode40-组合总和II

    原题 给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字…

    算法 2020年5月2日
    0730
  • leetcode300-最长上升子序列

    原题 给定一个无序的整数数组,找到其中最长上升子序列的长度。 示例: 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,10…

    算法 2020年3月14日
    0250

发表回复

登录后才能评论