Count The Repetitions

Description

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 ≤ 10⁶ and 1 ≤ n2 ≤ 10⁶. 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(javascript)

/*
 * @lc app=leetcode id=466 lang=javascript
 *
 * [466] Count The Repetitions
 */

// @lc code=start
// /** 这题关键是找到 s1 里和 s2 里相等的对应index
//  * 1: Top-down O(s1*n1*s2*n2)
//  * @param {string} s1
//  * @param {number} n1
//  * @param {string} s2
//  * @param {number} n2
//  * @return {number}
//  */
// const getMaxRepetitions = function (s1, n1, s2, n2) {
//   const length1 = s1.length * n1
//   const length2 = s2.length * n2
//   const memo = {}
//   const aux = (index1, index2) => {
//     const key = `${index1}-${index2}`
//     if (memo[key] !== undefined) {
//       return memo[key]
//     }
//     if (length2 - index2 > length1 - index1) {
//       return 0
//     }
//     if (index1 >= length1) {
//       return 0
//     }
//     const i = index1 % length1
//     const j = index2 % length2
//     const i1 = i % s1.length
//     const j1 = j % s2.length
//     if (s1[i1] === s2[j1]) {
//       memo[key] = aux(index1 + 1, index2 + 1) + (j === length2 - 1 ? 1 : 0)
//     } else {
//       memo[key] = aux(index1 + 1, index2)
//     }
//     return memo[key]
//   }
//   return aux(0, 0)
// }

/**
 * 2: Brute Force O(s1 * n1)
 * @param {string} s1
 * @param {number} n1
 * @param {string} s2
 * @param {number} n2
 * @return {number}
 */
const getMaxRepetitions = function (s1, n1, s2, n2) {
  let index = 0
  let count = 0
  for (let i = 1; i <= n1; i++) {
    for (let j = 0; j < s1.length; j++) {
      if (s1[j] === s2[index]) {
        index++
        if (index === s2.length) {
          count += 1
          index = 0
        }
      }
    }
  }
  return Math.floor((count) / n2)
}
// @lc code=end