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
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:
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, j, 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;
}
}
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