466. Count The Repetitions
Description
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 string s1
can be obtained from string s2
if we can remove some characters from s2
such that it becomes s1
.
- For example,
s1 = "abc"
can be obtained froms2 = "abdbec"
based on our definition by removing the bolded underlined characters.
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
.
Example 1:
Input: s1 = "acb", n1 = 4, s2 = "ab", n2 = 2 Output: 2
Example 2:
Input: s1 = "acb", n1 = 1, s2 = "acb", n2 = 1 Output: 1
Constraints:
1 <= s1.length, s2.length <= 100
s1
ands2
consist of lowercase English letters.1 <= n1, n2 <= 106
Solutions
Solution 1: Preprocessing + Iteration
We preprocess the string $s_2$ such that for each starting position $i$, we calculate the next position $j$ and the count of $s_2$ after matching a complete $s_1$, i.e., $d[i] = (cnt, j)$, where $cnt$ represents the count of $s_2$, and $j$ represents the next position in the string $s_2$.
Next, we initialize $j=0$, and then loop $n1$ times. Each time, we add $d[j][0]$ to the answer, and then update $j=d[j][1]$.
The final answer is the count of $s_2$ that can be matched by $n1$ $s_1$, divided by $n2$.
The time complexity is $O(m \times n + n_1)$, and the space complexity is $O(n)$. Where $m$ and $n$ are the lengths of $s_1$ and $s_2$ respectively.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
|
1 2 3 4 5 6 7 8 9 1 |