Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/466.html
466. Count The Repetitions (Hard)
Define S = [s,n] as the string S which consists of n connected strings s. For example, ["abc", 3] ="abcabcabc".
On the other hand, we define that string s1 can be obtained from string s2 if we can remove some characters from s2 such that it becomes s1. For example, “abc” can be obtained from “abdbec” based on our definition, but it can not be obtained from “acbbe”.
You are given two non-empty strings s1 and s2 (each at most 100 characters long) and two integers 0 ≤ n1 ≤ 106 and 1 ≤ n2 ≤ 106. Now consider the strings S1 and S2, where S1=[s1,n1] and S2=[s2,n2]. Find the maximum integer M such that [S2,M] can be obtained from S1.
Example:
Input: s1="acb", n1=4 s2="ab", n2=2 Return: 2
Related Topics:
Dynamic Programming
Solution 1.
See explanation here
// OJ: https://leetcode.com/problems/count-the-repetitions/
// Time: O(|s1| * n1) where |s1| is the length of s1
// Space: O(n1)
class Solution {
public:
int getMaxRepetitions(string s1, int n1, string s2, int n2) {
vector<int> repeatCount(n1 + 1, 0);
vector<int> nextIndex(n1 + 1, 0);
int j = 0, cnt = 0;
for (int k = 1; k <= n1; ++k) {
for (int i = 0; i < s1.size(); ++i) {
if (s1[i] == s2[j]) {
++j;
if (j == s2.size()) {
j = 0;
++cnt;
}
}
}
repeatCount[k] = cnt;
nextIndex[k] = j;
for (int start = 0; start < k; ++start) {
if (nextIndex[start] == j) {
int prefixCount = repeatCount[start];
int patternCount = (n1 - start) / (k - start) * (repeatCount[k] - prefixCount);
int suffixCount = repeatCount[start + (n1 - start) % (k - start)] - prefixCount;
return (prefixCount + patternCount + suffixCount) / n2;
}
}
}
return repeatCount[n1] / n2;
}
};
Solution 2.
Same idea as Solution 1, but use unordered_map to save computation. Reduce runtime from ~80ms to ~4ms.
// OJ: https://leetcode.com/problems/count-the-repetitions/
// Time: O(|s1| * n1) where |s1| is the length of s1
// Space: O(n1)
class Solution {
public:
int getMaxRepetitions(string s1, int n1, string s2, int n2) {
unordered_map<int, int> kToRepeatCount;
unordered_map<int, int> nextIndexToK;
kToRepeatCount[0] = 0;
nextIndexToK[0] = 0;
int j = 0, cnt = 0;
for (int k = 1; k <= n1; ++k) {
for (int i = 0; i < s1.size(); ++i) {
if (s1[i] == s2[j]) {
++j;
if (j == s2.size()) {
j = 0;
++cnt;
}
}
}
if (nextIndexToK.find(j) != nextIndexToK.end()) {
int start = nextIndexToK[j];
int prefixCount = kToRepeatCount[start];
int patternCount = (n1 - start) / (k - start) * (cnt - prefixCount);
int suffixCount = kToRepeatCount[start + (n1 - start) % (k - start)] - prefixCount;
return (prefixCount + patternCount + suffixCount) / n2;
}
kToRepeatCount[k] = cnt;
nextIndexToK[j] = k;
}
return kToRepeatCount[n1] / n2;
}
};
-
class Solution { public int getMaxRepetitions(String s1, int n1, String s2, int n2) { if (s1 == null || s2 == null) return 0; int length1 = s1.length(), length2 = s2.length(); if (length1 == 0 || length2 == 0 || n1 == 0 || n2 == 0) return 0; int gcd = gcd(n1, n2); n1 /= gcd; n2 /= gcd; int count = 0, index = 0; int[] counts = new int[length2 + 1]; int[] indices = new int[length2 + 1]; for (int i = 0; i < n1; i++) { for (int j = 0; j < length1; j++) { if (s1.charAt(j) == s2.charAt(index)) { if (index == length2 - 1) { count++; index = 0; } else index++; } } counts[i] = count; indices[i] = index; for (int j = 0; j < i; j++) { if (indices[j] == index) { int prevCount = counts[j]; int patternCount = (n1 - 1 - j) / (i - j) * (counts[i] - prevCount); int remainCount = counts[j + (n1 - 1 - j) % (i - j)] - prevCount; return (prevCount + patternCount + remainCount) / n2; } } } return counts[n1 - 1] / n2; } public int gcd(int num1, int num2) { if (num1 == 0 && num2 == 0) return 1; while (num1 != 0 && num2 != 0) { if (num1 > num2) { int temp = num1; num1 = num2; num2 = temp; } num2 %= num1; } return num1 == 0 ? num2 : num1; } } -
// OJ: https://leetcode.com/problems/count-the-repetitions/ // Time: O(|s1| * n1) where |s1| is the length of s1 // Space: O(n1) class Solution { public: int getMaxRepetitions(string s1, int n1, string s2, int n2) { vector<int> repeatCount(n1 + 1, 0); vector<int> nextIndex(n1 + 1, 0); int j = 0, cnt = 0; for (int k = 1; k <= n1; ++k) { for (int i = 0; i < s1.size(); ++i) { if (s1[i] == s2[j]) { ++j; if (j == s2.size()) { j = 0; ++cnt; } } } repeatCount[k] = cnt; nextIndex[k] = j; for (int start = 0; start < k; ++start) { if (nextIndex[start] == j) { int prefixCount = repeatCount[start]; int patternCount = (n1 - start) / (k - start) * (repeatCount[k] - prefixCount); int suffixCount = repeatCount[start + (n1 - start) % (k - start)] - prefixCount; return (prefixCount + patternCount + suffixCount) / n2; } } } return repeatCount[n1] / n2; } }; -
class Solution(object): def getMaxRepetitions(self, s1, n1, s2, n2): """ :type s1: str :type n1: int :type s2: str :type n2: int :rtype: int """ l2 = len(s2) dp = [0] * l2 for i in range(l2): j = i for c in s1: if c == s2[j % l2]: j += 1 if j == i: return 0 dp[i] = j - i idx = 0 for i in range(n1): idx += dp[idx % l2] return idx / l2 / n2