Problem

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 = "ab**dbe**c" 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.

Examples

Example 1

1
2

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

Example 2

1
2

Input: s1 = "acb", n1 = 1, s2 = "acb", n2 = 1
Output: 1

Constraints

  • 1 <= s1.length, s2.length <= 100
  • s1 and s2 consist of lowercase English letters.
  • 1 <= n1, n2 <= 106

Solution

Method 1 – Cycle Detection and Simulation

Intuition

We want to find the maximum number of times str2 (repeated n2 times) can be obtained from str1 (repeated n1 times) by deleting characters. Since n1 and n2 can be large, we use cycle detection to speed up the simulation. By tracking the position in s2 and the count of s2 matches after each s1 block, we can detect cycles and skip redundant work.

Approach

  1. Simulate matching s2 in s1, counting how many times s2 is matched after each s1 block.
  2. Track the position in s2 and the count of s2 matches for each s1 block in a map.
  3. If a cycle is detected (same s2 position seen before), calculate how many cycles fit in the remaining s1 blocks and skip them.
  4. Continue simulation for the remaining blocks.
  5. Return the total number of s2 matches divided by n2.

Code

 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
27
28

class Solution {
public:
    int getMaxRepetitions(string s1, int n1, string s2, int n2) {
        int l1 = s1.size(), l2 = s2.size();
        vector<int> indexr(l2+1), countr(l2+1);
        int idx = 0, cnt = 0;
        for (int k = 1; k <= n1; ++k) {
            for (int i = 0; i < l1; ++i) {
                if (s1[i] == s2[idx]) {
                    idx++;
                    if (idx == l2) {
                        cnt++;
                        idx = 0;
                    }
                }
            }
            if (indexr[idx]) {
                int pre = indexr[idx], pre_cnt = countr[idx];
                int cycle = (n1 - pre) / (k - pre);
                cnt = pre_cnt + cycle * (cnt - pre_cnt);
                k = pre + cycle * (k - pre);
            }
            indexr[idx] = k;
            countr[idx] = cnt;
        }
        return cnt / n2;
    }
};
 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

func getMaxRepetitions(s1 string, n1 int, s2 string, n2 int) int {
    l1, l2 := len(s1), len(s2)
    indexr := make([]int, l2+1)
    countr := make([]int, l2+1)
    idx, cnt := 0, 0
    for k := 1; k <= n1; k++ {
        for i := 0; i < l1; i++ {
            if s1[i] == s2[idx] {
                idx++
                if idx == l2 {
                    cnt++
                    idx = 0
                }
            }
        }
        if indexr[idx] > 0 {
            pre, pre_cnt := indexr[idx], countr[idx]
            cycle := (n1 - pre) / (k - pre)
            cnt = pre_cnt + cycle*(cnt-pre_cnt)
            k = pre + cycle*(k-pre)
        }
        indexr[idx] = k
        countr[idx] = cnt
    }
    return cnt / n2
}
 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
27

class Solution {
    public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
        int l1 = s1.length(), l2 = s2.length();
        int[] indexr = new int[l2+1], countr = new int[l2+1];
        int idx = 0, cnt = 0;
        for (int k = 1; k <= n1; ++k) {
            for (int i = 0; i < l1; ++i) {
                if (s1.charAt(i) == s2.charAt(idx)) {
                    idx++;
                    if (idx == l2) {
                        cnt++;
                        idx = 0;
                    }
                }
            }
            if (indexr[idx] > 0) {
                int pre = indexr[idx], pre_cnt = countr[idx];
                int cycle = (n1 - pre) / (k - pre);
                cnt = pre_cnt + cycle * (cnt - pre_cnt);
                k = pre + cycle * (k - pre);
            }
            indexr[idx] = k;
            countr[idx] = cnt;
        }
        return cnt / n2;
    }
}
 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
27
28
29
30

class Solution {
    fun getMaxRepetitions(s1: String, n1: Int, s2: String, n2: Int): Int {
        val l1 = s1.length; val l2 = s2.length
        val indexr = IntArray(l2+1)
        val countr = IntArray(l2+1)
        var idx = 0; var cnt = 0
        var k = 1
        while (k <= n1) {
            for (i in 0 until l1) {
                if (s1[i] == s2[idx]) {
                    idx++
                    if (idx == l2) {
                        cnt++
                        idx = 0
                    }
                }
            }
            if (indexr[idx] > 0) {
                val pre = indexr[idx]; val pre_cnt = countr[idx]
                val cycle = (n1 - pre) / (k - pre)
                cnt = pre_cnt + cycle * (cnt - pre_cnt)
                k = pre + cycle * (k - pre)
            }
            indexr[idx] = k
            countr[idx] = cnt
            k++
        }
        return cnt / n2
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

def getMaxRepetitions(s1: str, n1: int, s2: str, n2: int) -> int:
    l1, l2 = len(s1), len(s2)
    indexr = [0]*(l2+1)
    countr = [0]*(l2+1)
    idx = cnt = 0
    k = 1
    while k <= n1:
        for i in range(l1):
            if s1[i] == s2[idx]:
                idx += 1
                if idx == l2:
                    cnt += 1
                    idx = 0
        if indexr[idx]:
            pre, pre_cnt = indexr[idx], countr[idx]
            cycle = (n1 - pre) // (k - pre)
            cnt = pre_cnt + cycle * (cnt - pre_cnt)
            k = pre + cycle * (k - pre)
        indexr[idx] = k
        countr[idx] = cnt
        k += 1
    return cnt // n2
 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
27
28
29
30
31

impl Solution {
    pub fn get_max_repetitions(s1: String, n1: i32, s2: String, n2: i32) -> i32 {
        let l1 = s1.len(); let l2 = s2.len();
        let s1 = s1.as_bytes(); let s2 = s2.as_bytes();
        let mut indexr = vec![0; l2+1];
        let mut countr = vec![0; l2+1];
        let mut idx = 0; let mut cnt = 0;
        let mut k = 1;
        while k <= n1 {
            for i in 0..l1 {
                if s1[i] == s2[idx] {
                    idx += 1;
                    if idx == l2 {
                        cnt += 1;
                        idx = 0;
                    }
                }
            }
            if indexr[idx] > 0 {
                let pre = indexr[idx]; let pre_cnt = countr[idx];
                let cycle = (n1 - pre) / (k - pre);
                cnt = pre_cnt + cycle * (cnt - pre_cnt);
                k = pre + cycle * (k - pre);
            }
            indexr[idx] = k;
            countr[idx] = cnt;
            k += 1;
        }
        cnt / n2
    }
}
 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
27
28

class Solution {
    getMaxRepetitions(s1: string, n1: number, s2: string, n2: number): number {
        const l1 = s1.length, l2 = s2.length;
        const indexr = Array(l2+1).fill(0), countr = Array(l2+1).fill(0);
        let idx = 0, cnt = 0, k = 1;
        while (k <= n1) {
            for (let i = 0; i < l1; i++) {
                if (s1[i] === s2[idx]) {
                    idx++;
                    if (idx === l2) {
                        cnt++;
                        idx = 0;
                    }
                }
            }
            if (indexr[idx]) {
                const pre = indexr[idx], pre_cnt = countr[idx];
                const cycle = Math.floor((n1 - pre) / (k - pre));
                cnt = pre_cnt + cycle * (cnt - pre_cnt);
                k = pre + cycle * (k - pre);
            }
            indexr[idx] = k;
            countr[idx] = cnt;
            k++;
        }
        return Math.floor(cnt / n2);
    }
}

Complexity

  • ⏰ Time complexity: O(n1 * len(s1) + len(s2)), but cycle detection makes it much faster in practice.
  • 🧺 Space complexity: O(len(s2)), for tracking states.