Title
给你一个字符串 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 次。
Solve
前缀和+状态压缩
先来考虑最容易想到的暴力方法:枚举所有子串,遍历子串中的所有字符,统计元音字母出现的个数,如果符合条件就更新答案,不用想都知道这样肯定超时。
其实每个子串对应着一个区间,那么有什么方法可以在不重复遍历子串的前提下,快速求出这个区间里元音字母出现的次数呢?答案就是前缀和,对于一个区间,可以用两个前缀和的差值,得到其中某个字母出现次数。
对每个元音字母维护一个前缀和,定义pre[i][k]
表示在字符串前i
个字符中,第k
个元音字母一共出现的次数。
假设我们需要求出[l,r]
这个区间的子串是否满足条件,那么我们可以用pre[r][k]-pre[l-1][k]
,在O(1)
的时间得到第k
个元音字母出现的次数,对于每个元音字母都判断一下其是否出现偶数次即可。
利用前缀和优化了统计子串的时间复杂度,然而枚举所有子串的复杂度仍需要O(n2),还是不足以通过本题,还需要继续进行优化,避免枚举所有子串。
考虑枚举字符串的每个位置i
,计算以它结尾的满足条件的最长字符串长度。其实我们要做的就是快速找到最小的j∈[0,i)
,满足pre[i][k]−pre[j][k]
均为偶数,那么以i
结尾的最长字符串s[j+1,i]
长度就是i-j
。
但是单单利用前缀和,还是无法找到i
和j
相关的恒等式。这道题还有一个性质没有充分利用:目标子串中,每个元音字母都恰好出现了偶数次。
偶数这个条件其实告诉了我们,对于满足条件的子串,两个前缀和pre[i][k]
和pre[j][k]
的奇偶性一定是相同的,因此我们可以对前缀和稍作修改,从维护元音字母出现的次数改作维护元音字母出现次数的奇偶性。
这样我们只要实时维护每个元音字母出现的奇偶性,那么s[j+1,i]
满足条件当且仅当对于所有的k
,pre[i][k]
和pre[j][k]
的奇偶性都相等,此时我们就可以利用哈希表存储每一种奇偶性对应最早出现的位置,边遍历边更新答案。
其实到这里就差不多了,但是还可以进一步优化编码方式,如果直接以每个元音字母出现次数的奇偶性为哈希表中的键难免有些冗余,因此可以额外定义一个状态:
{
a: cnta, // a 出现次数的奇偶性
e: cnte, // e 出现次数的奇偶性
i: cnti, // i 出现次数的奇偶性
o: cnto, // o 出现次数的奇偶性
u: cntu // u 出现次数的奇偶性
}
将这么一个结构当做哈希表存储的键值,如果题目稍作修改扩大了字符集,那么维护起来可能会比较吃力。考虑到出现次数的奇偶性无非就两个值,0代表出现了偶数次,1代表出现了奇数次,我们可以将其压缩到一个二进制数中,第k
位的0或1代表了k
个元音字母出现的奇偶性,这样我们也不需要使用哈希表,直接用一个长度为32的数组来存储对应状态出现的最大位置即可。
为什么用 0 表示偶数?1 表示奇数?
因为这里我们打算用异或运算,而异或的性质是:如果对两个二进制做异或,会对其每一位进行位运算,如果相同则为 0,否则为 1。这和上面的性质非常相似。上面说奇偶性相同则位偶数,否则为奇数。因此很自然地用 0 表示偶数,1 表示奇数会更加方便。
复杂度分析
-
时间复杂度:O(n)
其中 n 为字符串 s 的长度。我们只需要遍历一遍字符串即可求得答案,因此时间复杂度为 O(n)。 -
空间复杂度:O(S)
其中 S 表示元音字母压缩成一个状态数的最大值,在本题中 S = 32。我们需要对应 S 大小的空间来存放每个状态第一次出现的位置,因此需要 O(S) 的空间复杂度。
Code
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