diff options
-rw-r--r-- | count_repititions.c | 43 | ||||
-rw-r--r-- | count_repititions.py | 52 |
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)) |