Count The Repetitions

hard dp string

Problem

Given s1·n1 and s2·n2 (concatenated), return the maximum integer M such that s2·M is a subsequence of s1·n1.

Inputs1 = "acb", n1 = 4, s2 = "ab", n2 = 2

Output2

Roll the matched offset until it repeats, then multiply through.

def get_max_repetitions(s1, n1, s2, n2):
    seen = {}  # offset -> (i, count2)
    j = count2 = 0
    for i in range(1, n1 + 1):
        for ch in s1:
            if ch == s2[j]:
                j += 1
                if j == len(s2):
                    j = 0; count2 += 1
        if j in seen:
            pi, pc = seen[j]
            cycle = i - pi
            cycles = (n1 - i) // cycle
            count2 += cycles * (count2 - pc)
            i += cycles * cycle
            seen.clear()
        else:
            seen[j] = (i, count2)
    return count2 // n2

function getMaxRepetitions(s1, n1, s2, n2) {
  const seen = new Map();
  let j = 0, count2 = 0;
  for (let i = 1; i <= n1; i++) {
    for (const ch of s1) {
      if (ch === s2[j]) {
        j++;
        if (j === s2.length) { j = 0; count2++; }
      }
    }
    if (seen.has(j)) {
      const [pi, pc] = seen.get(j);
      const cycle = i - pi;
      const cycles = Math.floor((n1 - i) / cycle);
      count2 += cycles * (count2 - pc);
      i += cycles * cycle;
      seen.clear();
    } else {
      seen.set(j, [i, count2]);
    }
  }
  return Math.floor(count2 / n2);
}

class Solution {
    public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
        Map seen = new HashMap<>();
        int j = 0, count2 = 0;
        for (int i = 1; i <= n1; i++) {
            for (char ch : s1.toCharArray()) {
                if (ch == s2.charAt(j)) {
                    j++;
                    if (j == s2.length()) { j = 0; count2++; }
                }
            }
            if (seen.containsKey(j)) {
                int[] prev = seen.get(j);
                int cycle = i - prev[0];
                int cycles = (n1 - i) / cycle;
                count2 += cycles * (count2 - prev[1]);
                i += cycles * cycle;
                seen.clear();
            } else seen.put(j, new int[]{ i, count2 });
        }
        return count2 / n2;
    }
}

int getMaxRepetitions(string s1, int n1, string s2, int n2) {
    unordered_map> seen;
    int j = 0, count2 = 0;
    for (int i = 1; i <= n1; i++) {
        for (char ch : s1) {
            if (ch == s2[j]) {
                j++;
                if (j == (int)s2.size()) { j = 0; count2++; }
            }
        }
        if (seen.count(j)) {
            auto [pi, pc] = seen[j];
            int cycle = i - pi;
            int cycles = (n1 - i) / cycle;
            count2 += cycles * (count2 - pc);
            i += cycles * cycle;
            seen.clear();
        } else seen[j] = {i, count2};
    }
    return count2 / n2;
}

Explanation

We're matching s2 as a subsequence inside many copies of s1, and n1 can be huge. The key insight is that the matching repeats in a cycle, so once we detect the cycle we can fast-forward through millions of copies instead of scanning them one by one.

We scan copies of s1 one at a time. A pointer j tracks how far we've matched into s2; each time j wraps past the end, we've completed one full s2 and bump count2.

After finishing each copy i, the pair "(current j)" is our state. We store seen[j] = (i, count2). If the same j shows up again, the work between the two sightings forms a repeating cycle of length cycle = i - pi that adds a fixed number of completed s2s.

We then jump ahead by as many whole cycles as fit in the remaining copies and add their contribution all at once: count2 += cycles * (count2 - pc). The final answer is count2 // n2, since the question asks how many copies of s2·n2 fit.

Example: s1="acb", n1=4, s2="ab", n2=2. The scan completes s2 four times across the copies, and 4 / 2 = 2.

Time: O(|s1| · n1) Space: O(|s1|)