In this guide, you will get 466. Count The Repetitions LeetCode Solution with the best time and space complexity. The solution to Count The Repetitions problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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 from s2 = “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.
466. Count The RepetitionsLeetCode Solution in C++
struct Record {
int count;
int nextIndex;
};
class Solution {
public:
int getMaxRepetitions(string s1, int n1, string s2, int n2) {
// records[i].count := the number of times that s2 starting from index i has
// been fully matched with s1
// records[i].nextIndex := the next index in s2 to be matched after
// completing a full match starting from index i
vector<Record> records;
for (int i = 0; i < s2.length(); ++i) {
int count = 0;
int nextIndex = i;
for (const char c : s1)
if (s2[nextIndex] == c)
if (++nextIndex == s2.length()) { // There's a match.
++count;
nextIndex = 0;
}
records.emplace_back(count, nextIndex);
}
int matches = 0; // the number of matches between `s1` x n1 and `s2`
int i = 0; // the index in `s2` to start matching
while (n1-- > 0) {
matches += records[i].count;
i = records[i].nextIndex;
}
return matches / n2;
}
};
/* code provided by PROGIEZ */
466. Count The RepetitionsLeetCode Solution in Java
class Solution {
public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
record Record(int count, int nextIndex) {}
// records[i].count := the number of times that s2 starting from index i has
// been fully matched with s1
// records[i].nextIndex := the next index in s2 to be matched after
// completing a full match starting from index i
List<Record> records = new ArrayList<>();
for (int i = 0; i < s2.length(); ++i) {
int count = 0;
int nextIndex = i;
for (final char c : s1.toCharArray())
if (s2.charAt(nextIndex) == c)
if (++nextIndex == s2.length()) { // There's a match.
++count;
nextIndex = 0;
}
records.add(new Record(count, nextIndex));
}
int matches = 0; // the number of matches between `s1` x n1 and `s2`
int i = 0; // the index in `s2` to start matching
while (n1-- > 0) {
matches += records.get(i).count;
i = records.get(i).nextIndex;
}
return matches / n2;
}
}
// code provided by PROGIEZ
466. Count The RepetitionsLeetCode Solution in Python
from dataclasses import dataclass
@dataclass
class Record:
count: int
nextIndex: int
class Solution:
def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:
# records[i].count := the number of times that s2 starting from index i has
# been fully matched with s1
# records[i].nextIndex := the next index in s2 to be matched after
# completing a full match starting from index i
records = []
for nextIndex in range(len(s2)):
count = 0
for c in s1:
if s2[nextIndex] == c:
nextIndex += 1
if nextIndex == len(s2): # There's a match.
count += 1
nextIndex = 0
records.append(Record(count, nextIndex))
matches = 0 # the number of matches between `s1` x n1 and `s2`
i = 0 # the index in `s2` to start matching
for _ in range(n1):
matches += records[i].count
i = records[i].nextIndex
return matches // n2
# code by PROGIEZ
