Skip to content

466. Count The Repetitions

  • Time: $O(|\texttt{s1}||\texttt{s2}| + \texttt{n1})$
  • Space: $O(|\texttt{s2}|)$
 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
32
33
34
35
36
37
struct Record {
  int count;
  int nextIndex;
};

class Solution {
 public:
  int getMaxRepetitions(string s1, int n1, string s2, int n2) {
    // records[i].count := the number of times that s2 starting from index i has
    // been fully matched with s1
    // records[i].nextIndex := the next index in s2 to be matched after
    // completing a full match starting from index i
    vector<Record> records;

    for (int i = 0; i < s2.length(); ++i) {
      int count = 0;
      int nextIndex = i;
      for (const char c : s1)
        if (s2[nextIndex] == c)
          if (++nextIndex == s2.length()) {  // There's a match.
            ++count;
            nextIndex = 0;
          }
      records.emplace_back(count, nextIndex);
    }

    int matches = 0;  // the number of matches between `s1` x n1 and `s2`
    int i = 0;        // the index in `s2` to start matching

    while (n1-- > 0) {
      matches += records[i].count;
      i = records[i].nextIndex;
    }

    return matches / 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
32
class Solution {
  public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
    record Record(int count, int nextIndex) {}
    // records[i].count := the number of times that s2 starting from index i has
    // been fully matched with s1
    // records[i].nextIndex := the next index in s2 to be matched after
    // completing a full match starting from index i
    List<Record> records = new ArrayList<>();

    for (int i = 0; i < s2.length(); ++i) {
      int count = 0;
      int nextIndex = i;
      for (final char c : s1.toCharArray())
        if (s2.charAt(nextIndex) == c)
          if (++nextIndex == s2.length()) { // There's a match.
            ++count;
            nextIndex = 0;
          }
      records.add(new Record(count, nextIndex));
    }

    int matches = 0; // the number of matches between `s1` x n1 and `s2`
    int i = 0;       // the index in `s2` to start matching

    while (n1-- > 0) {
      matches += records.get(i).count;
      i = records.get(i).nextIndex;
    }

    return matches / 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
32
33
34
35
from dataclasses import dataclass


@dataclass
class Record:
  count: int
  nextIndex: int


class Solution:
  def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:
    # records[i].count := the number of times that s2 starting from index i has
    # been fully matched with s1
    # records[i].nextIndex := the next index in s2 to be matched after
    # completing a full match starting from index i
    records = []

    for nextIndex in range(len(s2)):
      count = 0
      for c in s1:
        if s2[nextIndex] == c:
          nextIndex += 1
          if nextIndex == len(s2):  # There's a match.
            count += 1
            nextIndex = 0
      records.append(Record(count, nextIndex))

    matches = 0  # the number of matches between `s1` x n1 and `s2`
    i = 0  # the index in `s2` to start matching

    for _ in range(n1):
      matches += records[i].count
      i = records[i].nextIndex

    return matches // n2