The "Count The Repetitions" problem asks you to determine how many times a string s2 repeated n2 times can be found as a subsequence within another string s1 repeated n1 times.
s1 and s2, and two positive integers, n1 and n2.s1 with itself n1 times to form a long string S1.s2 with itself n2 times to form S2.M such that S2 repeated M times can be obtained as a subsequence of S1.Constraints:
n1, n2 ≤ 106len(s1), len(s2) ≤ 100
At first glance, you might think to generate the repeated strings and try to count how many times S2 can be matched as a subsequence within S1. However, with constraints as large as 106, this brute-force approach is not feasible due to memory and time limitations.
We need to realize that since s1 and s2 are both short but repeated many times, patterns or cycles will emerge as we simulate matching s2 as a subsequence within repeated s1. By identifying these cycles, we can "jump ahead" in our simulation, skipping redundant computations.
The key insight is to track how many times we've matched s2 as a subsequence after each repetition of s1, and to use a hash map to detect cycles in the matching process.
Here is the step-by-step approach to efficiently solve the problem:
s1 (repeated n1 times), and for each character, check if it matches the current character in s2.s2. When you finish s2, increment your s2_count and start matching from the beginning of s2 again.s1, record the current position in s2 and the total number of s2 matches so far.s2 index to the pair (s1_count, s2_count).s2 index again, a cycle has been detected.s1 repetitions, and update the total s2 matches accordingly.s1 repetitions after the cycles.s2 is matched as a subsequence, divided by n2 (since S2 is s2 repeated n2 times).This approach ensures we never explicitly construct the huge repeated strings, and efficiently computes the answer using cycle detection.
Let's walk through an example:
Input: s1 = "acb", n1 = 4, s2 = "ab", n2 = 2
s1 4 times: "acbacbacbacb"s2_count = 1)s2_count = 2)s2_count = 3)s2_count = 4)s2 repeats fit in s1:
s2 4 times in total.n2 = 2, we can fit 4 // 2 = 2 full S2 in S1.Output: 2
In this example, cycle detection is not strictly necessary due to the small input, but for large n1, cycles allow us to quickly compute the answer without simulating every repetition.
class Solution:
def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:
if n1 == 0:
return 0
s1_count, s2_count, index = 0, 0, 0
recall = dict()
while s1_count < n1:
for ch in s1:
if ch == s2[index]:
index += 1
if index == len(s2):
s2_count += 1
index = 0
s1_count += 1
if index in recall:
pre_s1_count, pre_s2_count = recall[index]
cycle_len = s1_count - pre_s1_count
cycle_s2 = s2_count - pre_s2_count
remain = (n1 - s1_count) // cycle_len
s1_count += remain * cycle_len
s2_count += remain * cycle_s2
else:
recall[index] = (s1_count, s2_count)
return s2_count // n2
class Solution {
public:
int getMaxRepetitions(string s1, int n1, string s2, int n2) {
if (n1 == 0) return 0;
int s1_count = 0, s2_count = 0, index = 0;
unordered_map<int, pair<int, int>> recall;
while (s1_count < n1) {
for (char ch : s1) {
if (ch == s2[index]) {
index++;
if (index == s2.size()) {
s2_count++;
index = 0;
}
}
}
s1_count++;
if (recall.count(index)) {
auto [pre_s1_count, pre_s2_count] = recall[index];
int cycle_len = s1_count - pre_s1_count;
int cycle_s2 = s2_count - pre_s2_count;
int remain = (n1 - s1_count) / cycle_len;
s1_count += remain * cycle_len;
s2_count += remain * cycle_s2;
} else {
recall[index] = {s1_count, s2_count};
}
}
return s2_count / n2;
}
};
class Solution {
public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
if (n1 == 0) return 0;
int s1Count = 0, s2Count = 0, index = 0;
Map<Integer, int[]> recall = new HashMap<>();
while (s1Count < n1) {
for (char ch : s1.toCharArray()) {
if (ch == s2.charAt(index)) {
index++;
if (index == s2.length()) {
s2Count++;
index = 0;
}
}
}
s1Count++;
if (recall.containsKey(index)) {
int[] pre = recall.get(index);
int cycleLen = s1Count - pre[0];
int cycleS2 = s2Count - pre[1];
int remain = (n1 - s1Count) / cycleLen;
s1Count += remain * cycleLen;
s2Count += remain * cycleS2;
} else {
recall.put(index, new int[]{s1Count, s2Count});
}
}
return s2Count / n2;
}
}
var getMaxRepetitions = function(s1, n1, s2, n2) {
if (n1 === 0) return 0;
let s1Count = 0, s2Count = 0, index = 0;
let recall = new Map();
while (s1Count < n1) {
for (let ch of s1) {
if (ch === s2[index]) {
index++;
if (index === s2.length) {
s2Count++;
index = 0;
}
}
}
s1Count++;
if (recall.has(index)) {
let [preS1Count, preS2Count] = recall.get(index);
let cycleLen = s1Count - preS1Count;
let cycleS2 = s2Count - preS2Count;
let remain = Math.floor((n1 - s1Count) / cycleLen);
s1Count += remain * cycleLen;
s2Count += remain * cycleS2;
} else {
recall.set(index, [s1Count, s2Count]);
}
}
return Math.floor(s2Count / n2);
};
The "Count The Repetitions" problem tests your ability to work with repeated strings and subsequences at scale. The key insight is to avoid brute-force construction of large strings and instead simulate the matching process while tracking state to detect cycles. By leveraging these cycles, we can efficiently "jump ahead" and compute the answer in a fraction of the time, making the solution both elegant and highly efficient for very large inputs.