# A Genarally Faster than O(Str1.Length * Str2.Length) Solution

• My code's run time is O(kL2logL1), where K is the rounds for s1 and s2' matching pattern to reoccur. For example:
S1:ababab
S2:bab
K = 3: because ababab|ababab contains 3 bab, after 3 repetitions of bab, the matching pattern reoccur.

So in average case, the code's run time is faster than O(l1*l2) But in a worst case, it can be as worse as O(L1 * L2 * lgL1).
One example of the worst case is：
S1:a....a (100 a's)
S2:a....a(99 a's)
K = 100: because S2 needs to repeat 100 times before the matching pattern reoccurs.

``````class Solution {
vector<int> charmap [256];
void buildmap(const string & s1)
{
for (int i = 0; i < s1.size(); ++i)
charmap[s1[i]].push_back(i);
}
public:
int getMaxRepetitions(string s1, int n1, string s2, int n2) {
buildmap(s1);
int rep = 0,  last_pos = -1, mult = 0, start_pos = -1, first_start_pos = -2, last_last_pos = -2, last_rep = 0;
vector<int> reps = {0};
while (true)
{
for (int i = 0; i < s2.size();)
{
auto & v = charmap[s2[i]];
if (v.empty())
return 0;
auto iter = upper_bound(v.begin(), v.end(), last_pos);
if (iter == v.end())
{
rep ++;
reps.push_back(mult);
last_pos = -1;
continue;
}
last_pos = *iter;
++ i;
}
start_pos = last_pos + 1;
for (int i = s2.size() - 1; i >= 0;)
{
auto & v = charmap[s2[i]];
auto iter = upper_bound(v.rbegin(), v.rend(), start_pos, std::greater<int>());
if (iter == v.rend())
{
start_pos = s1.size();
continue;
}
start_pos = *iter;
-- i;
}
mult ++;
if (start_pos == first_start_pos)
{
mult --;
break;
}
if (first_start_pos == -2)
first_start_pos = start_pos;
last_last_pos = last_pos;
last_rep = rep;
}
last_rep ++;
if (first_start_pos <= last_last_pos)
return ((n1 / last_rep) * mult + reps[n1 % last_rep])/n2;
return ((n1 - 1) / (last_rep - 1) * mult + reps[(n1 - 1) % (last_rep - 1) + 1])/n2;
}
};

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.