aboutsummaryrefslogtreecommitdiff
path: root/find_longest_special_substr1.c
diff options
context:
space:
mode:
Diffstat (limited to 'find_longest_special_substr1.c')
-rw-r--r--find_longest_special_substr1.c46
1 files changed, 46 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
+}