diff options
-rw-r--r-- | find_longest_special_substr1.c | 46 | ||||
-rw-r--r-- | find_longest_special_substr1.py | 37 |
2 files changed, 83 insertions, 0 deletions
diff --git a/find_longest_special_substr1.c b/find_longest_special_substr1.c new file mode 100644 index 0000000..d4b4ba6 --- /dev/null +++ b/find_longest_special_substr1.c @@ -0,0 +1,46 @@ +// 2981. Find Longest Special Substring That Occurs Thrice I +#include "leetcode.h" + +/* + * you are given a string 's' that consists of lowercase english letters. a + * string is called special if it is made up of only a single character. for + * example, the string 'abc' is not special, whereas the strongs 'ddd', 'zz', + * and 'f' are special. return the length of the longest special substring of + * 's' which occrs at least thrice, or -1 if no special substring occrs at least + * thrice. a substring is a contiguous non-empty sequence of characters within a + * string + */ + +bool helper(char *s, int n, int x) { + int cnt[26] = {0}, c = 0; + for (int i = 0; i < n; i++) { + while (s[c] != s[i]) + c++; + if (i - c + 1 >= x) + cnt[s[i] - 'a']++; + if (cnt[s[i] - 'a'] > 2) + return true; + } + return false; +} + +int maximumLength(char *s) { + int n = strlen(s), l = 1, r = n; + if (!helper(s, n, l)) + return -1; + while (l + 1 < r) { + int m = (l + r) / 2; + if (helper(s, n, m)) + l = m; + else + r = m; + } + return l; +} + +int main() { + char *s1 = "aaaa", *s2 = "abcdef", *s3 = "abcaba"; + printf("%d\n", maximumLength(s1)); // expect: 2 + printf("%d\n", maximumLength(s2)); // expect: -1 + printf("%d\n", maximumLength(s3)); // expect: 1 +} diff --git a/find_longest_special_substr1.py b/find_longest_special_substr1.py new file mode 100644 index 0000000..105e111 --- /dev/null +++ b/find_longest_special_substr1.py @@ -0,0 +1,37 @@ +# 2981. Find Longest Special Substring That Occurs Thrice I +from collections import defaultdict +from itertools import groupby + +""" +you are given a string 's' that consists of lowercase english letters. a +string is called special if it is made up of only a single character. for +example, the string 'abc' is not special, whereas the strongs 'ddd', 'zz', +and 'f' are special. return the length of the longest special substring of +'s' which occrs at least thrice, or -1 if no special substring occrs at least +thrice. a substring is a contiguous non-empty sequence of characters within a +string +""" + + +class Solution(object): + def maximumLength(self, s): + """ + :type s: str + :rtype: int + """ + d = defaultdict(int) + substr = ["".join(sub) for _, sub in groupby(s)] + for sub in substr: + d[sub] += 1 + if len(sub) > 1: + d[sub[1:]] += 2 + if len(sub) > 2: + d[sub[2:]] += 3 + return max(map(len, filter(lambda x: d[x] > 2, d)), default=-1) + + +if __name__ == "__main__": + obj = Solution() + print(obj.maximumLength(s="aaaa")) + print(obj.maximumLength(s="abcdef")) + print(obj.maximumLength(s="abcaba")) |