266 lines
8.0 KiB
Markdown
266 lines
8.0 KiB
Markdown
# 题目地址（1371. 每个元音包含偶数次的最长子字符串）
|
||
|
||
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 只包含小写英文字母。
|
||
|
||
```
|
||
|
||
## 暴力法 + 剪枝
|
||
|
||
### 思路
|
||
|
||
首先拿到这道题的时候，我想到第一反应是滑动窗口行不行。 但是很快这个想法就被我否定了，因为滑动窗口（这里是可变滑动窗口）我们需要扩张和收缩窗口大小，而这里不那么容易。因为题目要求的是奇偶性，而不是类似“元音出现最多的子串”等。
|
||
|
||
突然一下子没了思路。那就试试暴力法吧。暴力法的思路比较朴素和直观。 那就是`双层循环找到所有子串，然后对于每一个子串，统计元音个数，如果子串的元音个数都是偶数，则更新答案，最后返回最大的满足条件的子串长度即可`。
|
||
|
||
这里我用了一个小的 trick。枚举所有子串的时候，我是从最长的子串开始枚举的，这样我找到一个满足条件的直接返回就行了（early return），不必维护最大值。`这样不仅减少了代码量，还提高了效率。`
|
||
|
||
### 代码
|
||
|
||
代码支持：Python3
|
||
|
||
Python3 Code:
|
||
|
||
```python
|
||
|
||
class Solution:
|
||
def findTheLongestSubstring(self, s: str) -> int:
|
||
for i in range(len(s), 0, -1):
|
||
for j in range(len(s) - i + 1):
|
||
sub = s[j:j + i]
|
||
has_odd_vowel = False
|
||
for vowel in ['a', 'e', 'i', 'o', 'u']:
|
||
if sub.count(vowel) % 2 != 0:
|
||
has_odd_vowel = True
|
||
break
|
||
if not has_odd_vowel: return i
|
||
return 0
|
||
|
||
```
|
||
|
||
**复杂度分析**
|
||
|
||
- 时间复杂度：双层循环找出所有子串的复杂度是$O(n^2)$，统计元音个数复杂度也是$O(n)$，因此这种算法的时间复杂度为$O(n^3)$。
|
||
- 空间复杂度：$O(1)$
|
||
|
||
## 前缀和 + 剪枝
|
||
|
||
### 思路
|
||
|
||
上面思路中`对于每一个子串，统计元音个数`，我们仔细观察的话，会发现有很多重复的统计。那么优化这部分的内容就可以获得更好的效率。
|
||
|
||
对于这种连续的数字问题，这里我们考虑使用[前缀和](https://oi-wiki.org/basic/prefix-sum/)来优化。
|
||
|
||
经过这种空间换时间的策略之后，我们的时间复杂度会降低到$O(n ^ 2)$，但是相应空间复杂度会上升到$O(n)$，这种取舍在很多情况下是值得的。
|
||
|
||
### 代码
|
||
|
||
代码支持：Python3，Java
|
||
|
||
Python3 Code:
|
||
|
||
```python
|
||
class Solution:
|
||
i_mapper = {
|
||
"a": 0,
|
||
"e": 1,
|
||
"i": 2,
|
||
"o": 3,
|
||
"u": 4
|
||
}
|
||
def check(self, s, pre, l, r):
|
||
for i in range(5):
|
||
if s[l] in self.i_mapper and i == self.i_mapper[s[l]]: cnt = 1
|
||
else: cnt = 0
|
||
if (pre[r][i] - pre[l][i] + cnt) % 2 != 0: return False
|
||
return True
|
||
def findTheLongestSubstring(self, s: str) -> int:
|
||
n = len(s)
|
||
|
||
pre = [[0] * 5 for _ in range(n)]
|
||
|
||
# pre
|
||
for i in range(n):
|
||
for j in range(5):
|
||
if s[i] in self.i_mapper and self.i_mapper[s[i]] == j:
|
||
pre[i][j] = pre[i - 1][j] + 1
|
||
else:
|
||
pre[i][j] = pre[i - 1][j]
|
||
for i in range(n - 1, -1, -1):
|
||
for j in range(n - i):
|
||
if self.check(s, pre, j, i + j):
|
||
return i + 1
|
||
return 0
|
||
```
|
||
|
||
Java Code：
|
||
|
||
```java
|
||
class Solution {
|
||
public int findTheLongestSubstring(String s) {
|
||
|
||
int len = s.length();
|
||
|
||
if (len == 0)
|
||
return 0;
|
||
|
||
int[][] preSum = new int[len][5];
|
||
int start = getIndex(s.charAt(0));
|
||
if (start != -1)
|
||
preSum[0][start]++;
|
||
|
||
// preSum
|
||
for (int i = 1; i < len; i++) {
|
||
|
||
int idx = getIndex(s.charAt(i));
|
||
|
||
for (int j = 0; j < 5; j++) {
|
||
|
||
if (idx == j)
|
||
preSum[i][j] = preSum[i - 1][j] + 1;
|
||
else
|
||
preSum[i][j] = preSum[i - 1][j];
|
||
}
|
||
}
|
||
|
||
for (int i = len - 1; i >= 0; i--) {
|
||
|
||
for (int j = 0; j < len - i; j++) {
|
||
if (checkValid(preSum, s, i, i + j))
|
||
return i + 1
|
||
}
|
||
}
|
||
return 0
|
||
}
|
||
|
||
|
||
public boolean checkValid(int[][] preSum, String s, int left, int right) {
|
||
|
||
int idx = getIndex(s.charAt(left));
|
||
|
||
for (int i = 0; i < 5; i++)
|
||
if (((preSum[right][i] - preSum[left][i] + (idx == i ? 1 : 0)) & 1) == 1)
|
||
return false;
|
||
|
||
return true;
|
||
}
|
||
public int getIndex(char ch) {
|
||
|
||
if (ch == 'a')
|
||
return 0;
|
||
else if (ch == 'e')
|
||
return 1;
|
||
else if (ch == 'i')
|
||
return 2;
|
||
else if (ch == 'o')
|
||
return 3;
|
||
else if (ch == 'u')
|
||
return 4;
|
||
else
|
||
return -1;
|
||
}
|
||
}
|
||
```
|
||
|
||
**复杂度分析**
|
||
|
||
- 时间复杂度：$O(n^2)$。
|
||
- 空间复杂度：$O(n)$
|
||
|
||
## 前缀和 + 状态压缩
|
||
|
||
### 思路
|
||
|
||
前面的前缀和思路，我们通过空间（prefix）换取时间的方式降低了时间复杂度。但是时间复杂度仍然是平方，我们是否可以继续优化呢？
|
||
|
||
实际上由于我们只关心奇偶性，并不关心每一个元音字母具体出现的次数。因此我们可以使用`是奇数，是偶数`两个状态来表示，由于只有两个状态，我们考虑使用位运算。
|
||
|
||
我们使用 5 位的二进制来表示以 i 结尾的字符串中包含各个元音的奇偶性，其中 0 表示偶数，1 表示奇数，并且最低位表示 a，然后依次是 e，i，o，u。比如 `10110` 则表示的是包含偶数个 a 和 o，奇数个 e，i，u，我们用变量 `cur` 来表示。
|
||
|
||
为什么用 0 表示偶数？1 表示奇数？
|
||
|
||
回答这个问题，你需要继续往下看。
|
||
|
||
其实这个解法还用到了一个性质，这个性质是小学数学知识：
|
||
|
||
- 如果两个数字奇偶性相同，那么其相减一定是偶数。
|
||
- 如果两个数字奇偶性不同，那么其相减一定是奇数。
|
||
|
||
看到这里，我们再来看上面抛出的问题`为什么用 0 表示偶数？1 表示奇数？`。因为这里我们打算用异或运算，而异或的性质是：
|
||
|
||
如果对两个二进制做异或，会对其每一位进行位运算，如果相同则位 0，否则位 1。这和上面的性质非常相似。上面说`奇偶性相同则位偶数，否则为奇数`。因此很自然地`用 0 表示偶数？1 表示奇数`会更加方便。
|
||
|
||
### 代码
|
||
|
||
代码支持：Python3
|
||
|
||
Python3 Code:
|
||
|
||
```python
|
||
|
||
class Solution:
|
||
def findTheLongestSubstring(self, s: str) -> int:
|
||
mapper = {
|
||
"a": 1,
|
||
"e": 2,
|
||
"i": 4,
|
||
"o": 8,
|
||
"u": 16
|
||
}
|
||
seen = {0: -1}
|
||
res = cur = 0
|
||
|
||
for i in range(len(s)):
|
||
if s[i] in mapper:
|
||
cur ^= mapper.get(s[i])
|
||
# 全部奇偶性都相同，相减一定都是偶数
|
||
if cur in seen:
|
||
res = max(res, i - seen.get(cur))
|
||
else:
|
||
seen[cur] = i
|
||
return res
|
||
|
||
```
|
||
|
||
**复杂度分析**
|
||
|
||
- 时间复杂度：$O(n)$。
|
||
- 空间复杂度：$O(n)$
|
||
|
||
## 关键点解析
|
||
|
||
- 前缀和
|
||
- 状态压缩
|
||
|
||
## 相关题目
|
||
|
||
- [掌握前缀表达式真的可以为所欲为！](https://lucifer.ren/blog/2020/01/09/1310.xor-queries-of-a-subarray/)
|