在Python中查找元音计数为偶数的最长子串的长度
假设有一个字符串s(小写),我们必须查找每个元音出现偶数次的最长子字符串的长度。
因此,如果输入为s =”anewcoffeepot”,则输出将为10,因为子字符串”wcoffeepot”有两个元音”o”和”e”,它们都出现两次。
为了解决这个问题,我们将遵循以下步骤 −
- vowels:=将元音和数字值分配为a:0,e:1,i:2,o:3,u:4的映射
-
prefix:=空映射,并在其中插入一个键值对(0,−1)
-
mask:=0,n:=s的大小,res:=0
-
对于i在范围0到n中,执行以下操作
- 如果s[i]是一个元音,那么
- mask:=mask XOR (2^vowels[s[i]])
- 如果mask不在prefix中,那么
- prefix[mask]:= i
- 否则,
- res:=res和(i – prefix[mask])的最大值
- 如果s[i]是一个元音,那么
- 返回res
让我们看以下实现以获得更好的理解−
例子
class Solution:
def solve(self, s):
vowels = {"a": 0, "e": 1, "i": 2, "o": 3, "u": 4}
prefix = {0: −1}
mask = 0
n = len(s)
res = 0
for i in range(n):
if s[i] in vowels:
mask ^= 1 << vowels[s[i]]
if mask not in prefix:
prefix[mask] = i
else:
res = max(res, i − prefix[mask])
return res
ob = Solution()
s = "anewcoffeepot"
print(ob.solve(s))
输入
"anewcoffeepot"
输出
10