diff options
author | Jack Sangdahl <[email protected]> | 2024-09-14 19:51:29 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-09-14 19:51:29 -0600 |
commit | ccbfd54d4a6c45f92f556f4aab02b099703d197d (patch) | |
tree | 12e5291aca767283ddf5c47bf958c6c57e3a58ce | |
parent | 541bfbfc4625b97f3c6eb9978621ba3311beeed5 (diff) | |
download | leetcode-ccbfd54d4a6c45f92f556f4aab02b099703d197d.tar.gz leetcode-ccbfd54d4a6c45f92f556f4aab02b099703d197d.zip |
1371. find the longest substring containing vowels in even counts
Signed-off-by: Jack Sangdahl <[email protected]>
-rw-r--r-- | find_longest_substr_vowel.c | 47 | ||||
-rw-r--r-- | find_longest_substr_vowel.py | 29 |
2 files changed, 76 insertions, 0 deletions
diff --git a/find_longest_substr_vowel.c b/find_longest_substr_vowel.c new file mode 100644 index 0000000..57453f2 --- /dev/null +++ b/find_longest_substr_vowel.c @@ -0,0 +1,47 @@ +// 1371. Find the Longest Substring Containing Vowels in Even Counts +#include "leetcode.h" + +/* + * given the string 's', return the size of the longest substring containing + * each value an even number of times. that is 'a, e, i, o, u' must appear an + * even number of times. + */ + +#define FLIP(map, idx) ((map) ^ ((1) << (idx))) + +int vowel_idx(char vowel) { + switch (vowel) { + case 'a': + return 1; + case 'e': + return 2; + case 'i': + return 3; + case 'o': + return 4; + case 'u': + return 5; + default: + return 0; + } +} + +int findTheLongestSubstring(char *s) { + int n = strlen(s), memo[64] = {[0 ... 63] = -1}, curr = 0, max = 0; + unsigned char map = 0; + for (int i = 0; i < n; i++) { + map = FLIP(map, vowel_idx(*(s + i))) & -2; + if (map && *(memo + map) < 0) + *(memo + map) = i; + curr = i - *(memo + map); + max = curr >= max ? curr : max; + } + return max; +} + +int main() { + char *s1 = "eleetminicoworoep", *s2 = "leetcodeisgreate", *s3 = "bcbcbc"; + printf("%d\n", findTheLongestSubstring(s1)); // expect: 13 + printf("%d\n", findTheLongestSubstring(s2)); // expect: 5 + printf("%d\n", findTheLongestSubstring(s3)); // expect: 6 +} diff --git a/find_longest_substr_vowel.py b/find_longest_substr_vowel.py new file mode 100644 index 0000000..a9974ab --- /dev/null +++ b/find_longest_substr_vowel.py @@ -0,0 +1,29 @@ +# 1371. Find the Longest Substring Containing Vowels in Even Counts + +""" +given the string 's', return the size of the longest substring containing +each value an even number of times. that is 'a, e, i, o, u' must appear an +even number of times. +""" + + +class Solution(object): + def findTheLongestSubstring(self, s): + """ + :type s: str + :rtype: int + """ + seen = {0: -1} + ans, curr = 0, 0 + for i, j in enumerate(s): + curr ^= 1 << ("aeiou".find(j) + 1) >> 1 + seen.setdefault(curr, i) + ans = max(ans, i - seen[curr]) + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.findTheLongestSubstring("eleetminicoworoep")) + print(obj.findTheLongestSubstring("leetcodeisgreat")) + print(obj.findTheLongestSubstring("bcbcbc")) |