aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-09-14 19:51:29 -0600
committerJack Sangdahl <[email protected]>2024-09-14 19:51:29 -0600
commitccbfd54d4a6c45f92f556f4aab02b099703d197d (patch)
tree12e5291aca767283ddf5c47bf958c6c57e3a58ce
parent541bfbfc4625b97f3c6eb9978621ba3311beeed5 (diff)
downloadleetcode-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.c47
-rw-r--r--find_longest_substr_vowel.py29
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"))