aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--find_longest_special_substr1.c46
-rw-r--r--find_longest_special_substr1.py37
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"))