Define S = [s,n] as the string S which consists of n connected strings s. For example, ["abc", 3] ="abcabcabc".

On the other hand, 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, “abc” can be obtained from “abdbec” based on our definition, but it can not be obtained from “acbbe”.

You are given two non-empty strings s1 and s2 (each at most 100 characters long) and two integers 0 ≤ n1 ≤ 106 and 1 ≤ n2 ≤ 106. Now consider the strings S1 and S2, where S1=[s1,n1] and S2=[s2,n2]. Find the maximum integer M such that [S2,M] can be obtained from S1.

Example:

Input:
s1="acb", n1=4
s2="ab", n2=2

Return:
2

Solution


Approach #1 Brute force [Time Limit Exceeded]

Intuition

According to the question, we need to find such that is the largest subsequence that can be found in . is essentially and is and so, we can find the number of times repeats in , say . And the number of times repeats in is therefore . Simple.

Algorithm

  • Initialize and . represents the current index in to be checked against and represents the number of times repeats in .
  • Iterate over the variable from to :
    • Iterate over the variable from to :
      • If is equal to , increment .
      • If is equal to , this implies that has completed one repartition and hence set and increment the .
  • Return since, is .

C++

int getMaxRepetitions(string s1, int n1, string s2, int n2)
{
    int index = 0, repeat_count = 0;
    int s1_size = s1.size(), s2_size = s2.size();
    for (int i = 0; i < n1; i++) {
        for (int j = 0; j < s1_size; j++) {
            if (s1[j] == s2[index])
                ++index;
            if (index == s2_size) {
                index = 0;
                ++repeat_count;
            }
        }
    }
    return repeat_count / n2;
}

Complexity Analysis

  • Time complexity: .

    • We iterate over the entire length of string for times.
  • Space complexity: extra space for and .


Approach #2 A better brute force [Accepted]

Intuition

In Approach #1, we simply checked for repetition over the entire . However, could be quiet large and thus, is inefficient to iterate over complete . We can take advantage of the fact that is repeating and hence, we could find a pattern of repetition of in . Once, we get the repetition pattern, we can easy calculate how many times the pattern repeats in in .

But what's the pattern!

In approach #1, we kept which tells the index to search in . We try to see in the below illustration if this repeats itself after some fixed iterations of or not and if so, then how can we leverage it.

Count the repitition

After finding the repitition pattern, we can calculate the sum of repeating pattern, part before repitition and part left after repitition as the result in .

But will this repitition always take place?

Yes! By Pigeonhole principle, which states that if items are put into containers, with , then at least one container must contain more than one item. So, according to this, we are sure to find 2 same after scanning at max blocks of .

Algorithm

  • Intialize nd , which are same as in Approach #1.
  • Initialize 2 arrays, say and of size , initialized with 0. The size is based on the Pigeonhole principle as discussed above. The 2 arrays specifies the and at the start of each block.
  • Iterate over from to :
    • Iterate over from to :
      • If , increment .
      • If is equal to , set and increment .
    • Set and
    • Iterate over from to :

      • If we find the repitition, i.e. current , we calculate the count for block before the repitition starts, the repeating block and the block left after repitition pattern, which can be calculated as:

      • Sum the 3 counts and return the sum divided by , since
      • If no repetition is found, return .

C++

int getMaxRepetitions(string s1, int n1, string s2, int n2)
{
    if (n1 == 0)
        return 0;
    int indexr[s2.size() + 1] = { 0 }; // index at start of each s1 block
    int countr[s2.size() + 1] = { 0 }; // count of repititions till the present s1 block
    int index = 0, count = 0;
    for (int i = 0; i < n1; i++) {
        for (int j = 0; j < s1.size(); j++) {
            if (s1[j] == s2[index])
                ++index;
            if (index == s2.size()) {
                index = 0;
                ++count;
            }
        }
        countr[i] = count;
        indexr[i] = index;
        for (int k = 0; k < i; k++) {
            if (indexr[k] == index) {
                int prev_count = countr[k];
                int pattern_count = (countr[i] - countr[k]) * (n1 - 1 - k) / (i - k);
                int remain_count = countr[k + (n1 - 1 - k) % (i - k)] - countr[k];
                return (prev_count + pattern_count + remain_count) / n2;
            }
        }
    }
    return countr[n1 - 1] / n2;
}

Complexity analysis

  • Time complexity: .

    • According to the Pigeonhole principle, we need to iterate over only times at max.
  • Space complexity: extra space for and string.


Analysis written by @abhinavbansal0.