Missing Test Case - 466. Count The Repetitions #19426
Description
LeetCode Username
shell769324
Problem number, title, and link
https://leetcode.com/problems/count-the-repetitions
Category of the bug
- Problem description
- Solved examples
- Problem constraints
- Problem hints
- Incorrect or missing "Related Topics"
- Incorrect test Case (Output of test case is incorrect as per the problem statement)
- Missing test Case (Incorrect/Inefficient Code getting accepted because of missing test cases)
- Editorial
- Programming language support
Description of the bug
Didn't capture the case when a cycle consists of multiple s1 and s2 and the cycle starts partially
Language used for code
Code used for Submit/Run operation
class Solution {
public:
constexpr static int SIZE = 26;
int getMaxRepetitions(string s1, int n1, string s2, int n2) {
/*
cbca, cbca, cbca
*/
if (SIZE == 26) {
for (char& c : s1) {
c -= 'a';
}
for (char &c : s2) {
c -= 'a';
}
}
std::vector<std::set<int> > leftmost(SIZE);
std::unordered_set<char> included;
// slog(s)
for (int i = 0; i < s1.size(); i++) {
leftmost[s1[i]].insert(i);
included.insert(s1[i]);
}
for (char c : s2) {
if (included.find(c) == included.end()) {
return 0;
}
}
std::vector<std::vector<int> > graphs(s1.size(), std::vector<int>(SIZE));
// 26slog(s)
for (int i = 0; i < s1.size(); i++) {
for (char c : included) {
auto it = leftmost[c].upper_bound(i);
if (it == leftmost[c].end()) {
graphs[i][c] = *leftmost[c].begin();
} else {
graphs[i][c] = *it;
}
}
}
std::vector<std::pair<int, int> > dp;
int prev = -1;
int counter = 1;
std::vector<int> freqs(s1.size(), -1);
int cycle_length = 0;
int cycle_length2 = 0;
while (true) {
for (char c : s2) {
if (prev == -1) {
prev = *leftmost[s2[0]].begin();
} else {
int curr = graphs[prev][c];
if (curr <= prev) {
counter++;
}
prev = curr;
}
}
if (freqs[prev] != -1) {
cycle_length = counter - dp[freqs[prev]].first;
cycle_length2 = dp.size() - freqs[prev];
break;
}
freqs[prev] = dp.size();
dp.emplace_back(counter, prev);
}
int res = 0;
// has prefix
if (dp.back().first > cycle_length) {
if (cycle_length != 1) {
res++;
n1 -= dp.front().first;
} else {
res += std::find_if(dp.begin(), dp.end(), [cycle_length](auto p){ return p.first > cycle_length; }) - dp.begin();
n1--;
}
}
res += n1 / cycle_length * cycle_length2;
res += std::find_if(dp.begin(), dp.end(), [n1, cycle_length](auto p){ return p.first > n1 % cycle_length; }) - dp.begin();
return res / n2;
}
};
Expected behavior
s1 = "bababababa"
n1 = 5
s2 = "aab"
n2 = 1
Expected: 12