LeetCode - 1371 每个元音包含偶数次的最长子字符串（Java JS Python C）

2024-01-13 08:28
文章标签 java python leetcode 字符串 js 长子 偶数 元音 每个 1371

本文主要是介绍LeetCode - 1371 每个元音包含偶数次的最长子字符串（Java JS Python C），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目来源

1371. 每个元音包含偶数次的最长子字符串 - 力扣（LeetCode）

题目描述

给你一个字符串 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 只包含小写英文字母。

题目解析

本题最简单的思路就是双循环暴力枚举所有子串，然后计算子串内各个元音的数目。

但是这种思路肯定会超时。

我们枚举子串的目的，是为了统计子串中各元音字符的数量，而实现该需求的更优思路是利用前缀和。

前缀和的应用场景有非常鲜明的特点，如求解连续范围内的状态，实际例子有：求解任意区间的和。

本题其实也可以当成前缀和问题来看，我们遍历输入串，每遍历一个字符，则对应位置 i 就有一个前缀状态 preSum[i]，本题preSum[i] 表示 [0, i] 范围内各个元音字符的数量，具体表现为：

preSum[i] = {
    ‘a’：aCount，

    'e'：eCount，

    'i'：iCount，

    'o'：oCount，

    'u'：uCount
}

那么，如果我们要求解范围[i, j]子串的各个元音的数量，即可通过 preSum[j] - preSum[i-1] 得到。
更多前缀和知识请看：算法设计 - 前缀和 & 差分数列_算法设计 - 前缀和 & 差分数列_伏城之外的博客-csdn博客-CSDN博客

但是光靠前缀和，我们还是要枚举所有子串，依旧会超时。

本题要求我们求解最长的子串，子串范围内各个元音数量为偶数。我们假设：

preSum[j] 位置各个元音的数量分别为：aCount偶数，eCount奇数，iCount偶数，oCount偶数，uCount奇数

再假设 [i, j] 范围内各个元音的数量都为偶数，那么此时preSum[i-1]的各个元音的数量应该是多少呢？

答：必然和preSum[j] 对应元音的数量同奇偶性。因为：

  • 奇数 - 奇数 = 偶数
  • 偶数 - 偶数 = 偶数

比如 preSum[j] = {aCount: 8,  eCount: 3, iCount: 6, oCount: 4, uCount: 5}；

且  preSum[i-1] = {aCount: 2,  eCount: 1, iCount: 4, oCount: 2, uCount: 3}；

那么 [i, j] 范围内，各个元音的数量为：

  • aCount = 8 - 2 = 6
  • eCount = 3 - 1 = 2
  • iCount = 6 - 4 = 2
  • oCount = 4 - 2 = 2
  • uCount = 5 - 3 = 2

因此，当我们得到 preSum[j] 后，我们应该在 i - 1 ∈ [0, j - 1] 范围内找到一个 preSum[i-1] 和 preSum[j] 的各个元音同奇偶性的，且 i - 1要最小，这样得到 [i, j] 范围子串才是 [0, j] 范围内一个最长的且各个元音数量都为偶数的子串。

此时，逻辑虽然得到了优化，但是我们依旧要遍历 0 ~ j - 1 范围内的位置 i，且需要对比对应 preSum[i] 和 preSum[j] 的各个元音的奇偶性，这样依然会超时。

接下来要用到状态压缩了。

由于我们只关注各个元音的数量的奇偶性，即每个元音的数量要么为奇数，要么为偶数，假设我们用0表示偶数，用1表示奇数的话。

那么初始 preSum[0] 的各个元音的状态就可以表示为二进制数：00000

各个二进制位和对应元音对应，如上图所示，当二进制位值为0时，表示对应元音数量为偶数个，当二进制位值为1时，表示对应元音数量为奇数个。

这样我们就完成了 preSum[i] 的状态压缩。

那么状态压缩后的preSum[j] 和 preSum[j+1] 如何进行前缀和累进呢？

假设 j+1 位置的字符是 'e'，那么代表，preSum[j] 的二进制数 中 'e' 对应的位的性质反转，即奇变偶，偶变奇。

比如 preSum[j] = 01010，而 s[j+1] 字符是 'e'，则 preSum[j+1] = 00010

此时我们完全可以用异或运算从preSum[j]得出preSum[j+1]的结果，比如 s[j+1] == 'e'，则

preSum[j + 1] = preSum[j] ^ 01000

其中 01000 代表是新增一个'e'字符，同理

  • 10000 代表新增一个 'a' 字符
  • 01000 代表新增一个 'e' 字符
  • 00100 代表新增一个 'i' 字符
  • 00010 代表新增一个 'o' 字符
  • 00001 代表新增一个 'u' 字符

接下来就是，比较preSum[i] 和 preSum[j] 的各个元音的奇偶性是否一致，就可以直接将对应二进制数进行值比较即可，值相同，则奇偶性一致，否则不一致。

比如：preSum[i-1] = 01010，preSum[j] = 01010，那么二者的各个元音的奇偶性就一致。

当我们完成preSum[i]的状态压缩后，我们就可以定义一个哈希表map来记录某个压缩状态最早出现的位置，map的key时压缩状态，val时该压缩状态的最早出现位置。

即：我们求解[0, j]范围前缀子串的压缩状态status = preSum[j]后：

  • 如果map存在key=status，那么status状态最早出现位置为 map[staus]，我们定义 i = map[status]，那么i，j位置的前缀子串内部的各个元音的数量是同奇偶性的，即 [i+1, j] 范围内子串的各个元音的数量B必然都是偶数，[i+1, j] 范围子串是一个符合要求的子串，我们需要记录该子串的长度 j - (i + 1) + 1 = j - i
  • 如果 map 不存在 key == status，那么status状态最早出现的位置就是 j，我们需要记录 map[status] = j

按照逻辑，我们只要遍历一遍字符串s，即可找到最长的目标子串。

JS算法源码

/*** @param {string} s* @return {number}*/
var findTheLongestSubstring = function (s) {// "前缀子串"中各个元音的奇偶状态// 00000// aeiou// 元音字母和二进制位的对应关系如上，如果二进制位值位0，代表对应元音字符数量有偶数个，如果二进制位值为1，代表对应元音字符数量有奇数个// 初始未遍历时，没有子串，此时各个元音的数量都为0，即偶数个，因此所有二进制位值位0let status = 0b00000;// map记录某个状态的最早出现位置// 压缩状态用五位二进制数表示，因此最多有32种状态const map = new Array(32).fill(-2); // -2是一个不可能的位置,即初始时所有状态都未出现过// 00000 状态对应的十进制数为0，最早出现位置是-1，即未遍历，没有子串时map[0] = -1;// 记录最长的符合要求的子串长度let maxLen = 0;for (let i = 0; i < s.length; i++) {// 如果遍历的字符s[i]是元音字母，则变更对应二进制位的奇偶性switch (s[i]) {case "a":status ^= 0b10000;break;case "e":status ^= 0b01000;break;case "i":status ^= 0b00100;break;case "o":status ^= 0b00010;break;case "u":status ^= 0b00001;break;}// 如果对应状态的最早出现位置为-2，表示没有出现过对应状态，否则map[status]即status状态最早出现的位置if (map[status] != -2) {// 当前位置 i 的状态为status，而最早出现status状态的位置是 map[status]，两个位置同奇偶性，因此他们形成的范围内子串是符合要求的maxLen = Math.max(maxLen, i - map[status]);} else {// 如果对应状态之前未出现过，则当前位置 i 就是该状态的最早出现位置map[status] = i;}}return maxLen;
};

Java算法源码

import java.util.Arrays;class Solution {public int findTheLongestSubstring(String s) {// "前缀子串"中各个元音的奇偶状态// 00000// aeiou// 元音字母和二进制位的对应关系如上，如果二进制位值位0，代表对应元音字符数量有偶数个，如果二进制位值为1，代表对应元音字符数量有奇数个// 初始未遍历时，没有子串，此时各个元音的数量都为0，即偶数个，因此所有二进制位值位0int status = 0b00000;// map记录某个状态的最早出现位置// 压缩状态用五位二进制数表示，因此最多有32种状态int[] map = new int[32]; // -2是一个不可能的位置Arrays.fill(map, -2);// 00000 状态对应的十进制数为0，最早出现位置是-1，即未遍历，没有子串时map[0] = -1;// 记录最长的符合要求的子串长度int maxLen = 0;for (int i = 0; i < s.length(); i++) {// 如果遍历的字符s[i]是元音字母，则变更对应二进制位的奇偶性switch (s.charAt(i)) {case 'a':status ^= 0b10000;break;case 'e':status ^= 0b01000;break;case 'i':status ^= 0b00100;break;case 'o':status ^= 0b00010;break;case 'u':status ^= 0b00001;break;}// 如果对应状态的最早出现位置为-2，表示没有出现过对应状态，否则map[status]即status状态最早出现的位置if (map[status] != -2) {// 当前位置 i 的状态为status，而最早出现status状态的位置是 map[status]，两个位置同奇偶性，因此他们形成的范围内子串是符合要求的maxLen = Math.max(maxLen, i - map[status]);} else {// 如果对应状态之前未出现过，则当前位置 i 就是该状态的最早出现位置map[status] = i;}}return maxLen;}
}

Python算法源码

class Solution(object):def findTheLongestSubstring(self, s):""":type s: str:rtype: int"""# "前缀子串"中各个元音的奇偶状态# 00000# aeiou# 元音字母和二进制位的对应关系如上，如果二进制位值位0，代表对应元音字符数量有偶数个，如果二进制位值为1，代表对应元音字符数量有奇数个# 初始未遍历时，没有子串，此时各个元音的数量都为0，即偶数个，因此所有二进制位值位0status = 0b00000# map记录某个状态的最早出现位置, -2是一个不可能的位置, 即初始时各个状态都没有出现过# 压缩状态用五位二进制数表示，因此最多有32种状态map = [-2] * 32# 00000 状态对应的十进制数为0，最早出现位置是-1，即未遍历，没有子串时map[0] = -1# 记录最长的符合要求的子串长度maxLen = 0for i in range(len(s)):c = s[i]# 如果遍历的字符s[i]是元音字母，则变更对应二进制位的奇偶性if c == 'a':status ^= 0b10000elif c == 'e':status ^= 0b01000elif c == 'i':status ^= 0b00100elif c == 'o':status ^= 0b00010elif c == 'u':status ^= 0b00001# 如果对应状态的最早出现位置为-2，表示没有出现过对应状态，否则map[status]即status状态最早出现的位置if map[status] != -2:# 当前位置 i 的状态为status，而最早出现status状态的位置是 map[status]，两个位置同奇偶性，因此他们形成的范围内子串是符合要求的maxLen = max(maxLen, i - map[status])else:# 如果对应状态之前未出现过，则当前位置 i 就是该状态的最早出现位置map[status] = ireturn maxLen

C算法源码

int findTheLongestSubstring(char* s) {// "前缀子串"中各个元音的奇偶状态// 00000// aeiou// 元音字母和二进制位的对应关系如上，如果二进制位值位0，代表对应元音字符数量有偶数个，如果二进制位值为1，代表对应元音字符数量有奇数个// 初始未遍历时，没有子串，此时各个元音的数量都为0，即偶数个，因此所有二进制位值位0int status = 0b00000;// map记录某个状态的最早出现位置// 压缩状态用五位二进制数表示，因此最多有32种状态int map[32];for(int i=0; i<32; i++) map[i] = -2;  // -2是一个不可能的位置,即初始时所有状态都未出现过// 00000 状态对应的十进制数为0，最早出现位置是-1，即未遍历，没有子串时map[0] = -1;// 记录最长的符合要求的子串长度int maxLen = 0;int i=0;while(s[i] != '\0') {char c = s[i];// 如果遍历的字符s[i]是元音字母，则变更对应二进制位的奇偶性switch(c) {case 'a':status ^= 0b10000;break;case 'e':status ^= 0b01000;break;case 'i':status ^= 0b00100;break;case 'o':status ^= 0b00010;break;case 'u':status ^= 0b00001;break;}// 如果对应状态的最早出现位置为-2，表示没有出现过对应状态，否则map[status]即status状态最早出现的位置if (map[status] != -2) {// 当前位置 i 的状态为status，而最早出现status状态的位置是 map[status]，两个位置同奇偶性，因此他们形成的范围内子串是符合要求的maxLen = (int) fmax(maxLen, i - map[status]);} else {// 如果对应状态之前未出现过，则当前位置 i 就是该状态的最早出现位置map[status] = i;}i++;}return maxLen;
}

这篇关于LeetCode - 1371 每个元音包含偶数次的最长子字符串（Java JS Python C）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/600812。

相关文章

Java五子棋之坐标校正

Java五子棋之坐标校正

上篇针对了Java项目中的解构思维，在这篇内容中我们不妨从整体项目中拆解拿出一个非常重要的五子棋逻辑实现：坐标校正，我们如何使漫无目的鼠标点击变得有序化和可控化呢？ 目录 一、从鼠标监听到获取坐标 1.MouseListener和MouseAdapter 2.mousePressed方法 二、坐标校正的具体实现方法 1.关于fillOval方法 2.坐标获取 3.坐标转换 4.坐
阅读更多...
Spring Cloud：构建分布式系统的利器

Spring Cloud：构建分布式系统的利器

引言 在当今的云计算和微服务架构时代，构建高效、可靠的分布式系统成为软件开发的重要任务。Spring Cloud 提供了一套完整的解决方案，帮助开发者快速构建分布式系统中的一些常见模式（例如配置管理、服务发现、断路器等）。本文将探讨 Spring Cloud 的定义、核心组件、应用场景以及未来的发展趋势。 什么是 Spring Cloud Spring Cloud 是一个基于 Spring
阅读更多...
Javascript高级程序设计(第四版)--学习记录之变量、内存

Javascript高级程序设计(第四版)--学习记录之变量、内存

原始值与引用值 原始值：简单的数据即基础数据类型，按值访问。 引用值：由多个值构成的对象即复杂数据类型，按引用访问。 动态属性 对于引用值而言，可以随时添加、修改和删除其属性和方法。 let person = new Object();person.name = 'Jason';person.age = 42;console.log(person.name,person.age);//'J
阅读更多...
java8的新特性之一（Java Lambda表达式）

java8的新特性之一（Java Lambda表达式）

1：Java8的新特性 Lambda 表达式： 允许以更简洁的方式表示匿名函数（或称为闭包）。可以将Lambda表达式作为参数传递给方法或赋值给函数式接口类型的变量。 Stream API： 提供了一种处理集合数据的流式处理方式，支持函数式编程风格。 允许以声明性方式处理数据集合（如List、Set等）。提供了一系列操作，如map、filter、reduce等，以支持复杂的查询和转
阅读更多...
Java面试八股之怎么通过Java程序判断JVM是32位还是64位

Java面试八股之怎么通过Java程序判断JVM是32位还是64位

怎么通过Java程序判断JVM是32位还是64位 可以通过Java程序内部检查系统属性来判断当前运行的JVM是32位还是64位。以下是一个简单的方法： public class JvmBitCheck {public static void main(String[] args) {String arch = System.getProperty("os.arch");String dataM
阅读更多...
详细分析Springmvc中的@ModelAttribute基本知识（附Demo）

详细分析Springmvc中的@ModelAttribute基本知识（附Demo）

目录 前言1. 注解用法1.1 方法参数1.2 方法1.3 类 2. 注解场景2.1 表单参数2.2 AJAX请求2.3 文件上传 3. 实战4. 总结 前言 将请求参数绑定到模型对象上，或者在请求处理之前添加模型属性 可以在方法参数、方法或者类上使用 一般适用这几种场景： 表单处理：通过 @ModelAttribute 将表单数据绑定到模型对象上预处理逻辑：在请求处理之前
阅读更多...
eclipse运行springboot项目，找不到主类

eclipse运行springboot项目，找不到主类

解决办法尝试了很多种，下载sts压缩包行不通。最后解决办法如图： help--->Eclipse Marketplace--->Popular--->找到Spring Tools 3---->Installed。
阅读更多...
JAVA读取MongoDB中的二进制图片并显示在页面上

JAVA读取MongoDB中的二进制图片并显示在页面上

1：Jsp页面： <td><img src="${ctx}/mongoImg/show"></td> 2：xml配置： <?xml version="1.0" encoding="UTF-8"?><beans xmlns="http://www.springframework.org/schema/beans"xmlns:xsi="http://www.w3.org/2001
阅读更多...
Java面试题：通过实例说明内连接、左外连接和右外连接的区别

Java面试题：通过实例说明内连接、左外连接和右外连接的区别

在 SQL 中，连接（JOIN）用于在多个表之间组合行。最常用的连接类型是内连接（INNER JOIN）、左外连接（LEFT OUTER JOIN）和右外连接（RIGHT OUTER JOIN）。它们的主要区别在于它们如何处理表之间的匹配和不匹配行。下面是每种连接的详细说明和示例。 表示例 假设有两个表：Customers 和 Orders。 Customers CustomerIDCus
阅读更多...
22.手绘Spring DI运行时序图

22.手绘Spring DI运行时序图

1.依赖注入发生的时间 当Spring loC容器完成了 Bean定义资源的定位、载入和解析注册以后,loC容器中已经管理类Bean 定义的相关数据，但是此时loC容器还没有对所管理的Bean进行依赖注入，依赖注入在以下两种情况 发生： 、用户第一次调用getBean()方法时，loC容器触发依赖注入。 、当用户在配置文件中将＜bean＞元素配置了 lazy-init二false属性,即让
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2