aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--count_repititions.c43
-rw-r--r--count_repititions.py52
2 files changed, 95 insertions, 0 deletions
diff --git a/count_repititions.c b/count_repititions.c
new file mode 100644
index 0000000..3202487
--- /dev/null
+++ b/count_repititions.c
@@ -0,0 +1,43 @@
+// 466. Count The Repetitions
+#include "leetcode.h"
+
+/*
+ * we define 'str = [s, n]' as the string 'str' which consists of the string 's'
+ * concatenated 'n' times. for example 'str == ["abc", 3] = "abcabcabc'. we
+ * define that strng 's1' can be obtained from string 's2' if we can remove some
+ * characters from 's2' such that it becomes 's1'. you are given two strings
+ * 's1' and 's2' and two integers 'n1' and 'n2'. you have the two strings 'str1
+ * = [s1, n1]' and 'str2 = [s2, n2]'. return the maximum integer 'm' such that
+ * 'str = [str2, m]' can be obtained from 'str1'
+ */
+
+int getMaxRepetitions(char *s1, int n1, char *s2, int n2) {
+ int a = 0, b = 0, c = 0, d = 0, e = -1, f = 0;
+ char s1r, s2r = s2[b];
+ while (c < n1) {
+ if (!(s1r = s1[a++])) {
+ c++;
+ a = 0;
+ continue;
+ }
+ if (s2r == s1r) {
+ if (e == -1)
+ e = a;
+ else if ((e == a) && (b == 0))
+ return ((((n1 * d) / c) - (f == c)) / n2);
+ s2r = s2[++b];
+ }
+ if (!s2r) {
+ s2r = s2[(b = 0)];
+ d++;
+ f = c;
+ }
+ }
+ return (d / n2);
+}
+
+int main() {
+ char *s11 = "acb", *s21 = "ab", *s12 = "acb", *s22 = "acb";
+ printf("%d\n", getMaxRepetitions(s11, 4, s21, 2)); // expect: 2
+ printf("%d\n", getMaxRepetitions(s12, 1, s22, 1)); // expect: 1
+}
diff --git a/count_repititions.py b/count_repititions.py
new file mode 100644
index 0000000..320fd01
--- /dev/null
+++ b/count_repititions.py
@@ -0,0 +1,52 @@
+# 466. Count The Repetitions
+
+"""
+we define 'str = [s, n]' as the string 'str' which consists of the string 's'
+concatenated 'n' times. for example 'str == ["abc", 3] = "abcabcabc'. we
+define that strng 's1' can be obtained from string 's2' if we can remove some
+characters from 's2' such that it becomes 's1'. you are given two strings
+'s1' and 's2' and two integers 'n1' and 'n2'. you have the two strings 'str1
+= [s1, n1]' and 'str2 = [s2, n2]'. return the maximum integer 'm' such that
+'str = [str2, m]' can be obtained from 'str1'
+"""
+
+
+class Solution(object):
+ def getMaxRepetitions(self, s1, n1, s2, n2):
+ """
+ :type s1: str
+ :type n1: int
+ :type s2: str
+ :type n2: int
+ :rtype: int
+ """
+ start = {}
+ s1r, s2r, s2_idx = 0, 0, 0
+ while s1r < n1:
+ s1r += 1
+ for ch in s1:
+ if ch == s2[s2_idx]:
+ s2_idx += 1
+ if s2_idx == len(s2):
+ s2r += 1
+ s2_idx = 0
+ if s2_idx in start:
+ prev_s1r, prev_s2r = start[s2_idx]
+ circle_s1r, circle_s2r = s1r - prev_s1r, s2r - prev_s2r
+ ans = n1 - prev_s1r
+ left_s1r = (n1 - prev_s1r) % circle_s1r + prev_s1r
+ for key in start:
+ val = start[key]
+ if val[0] == left_s1r:
+ ans += val[1]
+ break
+ return ans
+ else:
+ start[s2_idx] = (s1r, s2r)
+ return s2r
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.getMaxRepetitions(s1="acb", n1=4, s2="ab", n2=2))
+ print(obj.getMaxRepetitions(s1="acb", n1=1, s2="acb", n2=1))