Efficient JS Solution using binary jump (Beat 100% time)
\n\nLOL I\'m faster than the "Bestest solution in JavaScript".\n\n# Complexity\n- let l_1 = s_1.length, l_2 = s_2.length\n- Time complexity: O(l_1^2l_2)\n- Spac
![image.png](https://assets.leetcode.com/users/images/1926e9d7-dc9f-45f4-86f7-3a02975f0365_1698428384.7085106.png)\n\nLOL I\'m faster than the "Bestest solution in JavaScript".\n\n# Complexity\n- let $$l_1 = s_1.length$$, $$l_2 = s_2.length$$\n- Time complexity: $$O(l_1^2l_2)$$\n- Space complexity: $$O(l_1log(l_1n_1 / l_2))$$\n\n# Code\n```js\n//#region Tensor\n/**\n * @template TItem\n */\nclass Tensor {\n  /**\n   * @param {number} capacity The max capacity of the tensor\n   * @param {number[] | undefined} dimensions\n   */\n  constructor(capacity, dimensions) {\n    /**\n     * @private\n     * @type {TItem[]}\n     */\n    this._data = Array(capacity).fill();\n\n    /**\n     * @private\n     * @type {number[]}\n     */\n    this._dimensions;\n\n    /**\n     * @private\n     * @type {number}\n     */\n    this._total = 0;\n\n    this.resize(dimensions);\n\n    /**\n     * An array of indices whole sole purpose is to avoid recreating array for some operations such as **forEach**\n     * @type {number[]}\n     * @private\n     */\n    this.__indices = [];\n  }\n\n  /**\n   * @param {...number} dimensions\n   */\n  resize(...dimensions) {\n    this._dimensions = dimensions;\n    if (!this._dimensions?.length) this._total = 0;\n    else {\n      this._total = 1;\n      for (let i = 0; i < this._dimensions.length; i++)\n        this._total *= this._dimensions[i];\n    }\n  }\n\n  /**\n   * @param {TItem} value\n   */\n  fill(value) {\n    if (!this._dimensions)\n      throw `Call "resize" to initialize the dimensions of the Tensor first.`;\n    this._data.fill(value, 0, this._total);\n  }\n\n  /**\n   * @private\n   * @param {number[]} indices\n   */\n  _getFlattenIndex(indices) {\n    if (!this._dimensions)\n      throw `Call "resize" to initialize the dimensions of the Tensor first.`;\n    let n = indices.length;\n    if (n != this._dimensions.length)\n      throw `The number of dimensions does not match`;\n    if (!n) return 0;\n\n    if (indices[0] < 0 || indices[0] >= this._dimensions[0])\n      throw `The ${0}-th dimension should be in range [0, ${\n        this._dimensions[0]\n      })`;\n\n    let result = indices[0];\n    for (let i = 1; i < n; i++) {\n      if (indices[i] < 0 || indices[i] >= this._dimensions[i])\n        throw `The ${i}-th dimension should be in range [0, ${this._dimensions[i]})`;\n      result = result * this._dimensions[i] + indices[i];\n    }\n\n    return result;\n  }\n\n  /**\n   * @param  {...number} indices\n   */\n  at(...indices) {\n    return this._data[this._getFlattenIndex(indices)];\n  }\n\n  /**\n   * @param  {TItem} value\n   * @param  {...number} indices\n   */\n  set(value, ...indices) {\n    this._data[this._getFlattenIndex(indices)] = value;\n  }\n\n  /**\n   * WARNING: Don\'t mutate indices array\n   * @param {(value: TItem, indices: number[], set: (value: TItem) => void) =>} cb\n   */\n  forEach(cb) {\n    if (!this._dimensions)\n      throw `Call "resize" to initialize the dimensions of the Tensor first.`;\n\n    const indices = this.__indices;\n    const d = this._dimensions.length;\n\n    while (indices.length < d) indices.push(0);\n    indices.fill(0, 0, d);\n\n    let i = 0;\n    const set = (value) => {\n      this._data[i] = value;\n    };\n\n    cb(this._data[0], indices, set);\n\n    for (i = 1; i < this._total; i++) {\n      let j = d;\n      do {\n        j--;\n        indices[j]++;\n        if (indices[j] == this._dimensions[j]) indices[j] = 0;\n      } while (!indices[j]);\n\n      cb(this._data[i], indices, set);\n    }\n  }\n}\n//#endregion\n\nlet laps = new Tensor(2700);\nlet jump = new Tensor(2700);\n\n/**\n * @param {string} s1\n * @param {number} n1\n * @param {string} s2\n * @param {number} n2\n * @return {number}\n */\nvar getMaxRepetitions = function (s1, n1, s2, n2) {\n  let l1 = s1.length;\n  let l2 = s2.length;\n\n  laps.resize(l1, 27);\n  jump.resize(l1, 27);\n\n  for (let i = 0; i < l1; i++) {\n    let lap = i? 0 : 1;\n    let i1 = i;\n    let i2 = 0;\n\n    while (true) {\n      if (s1[i1] == s2[i2]) i2++;\n      i1++;\n\n      if (i1 == l1) {\n        if (i2 != l2) lap++;\n        i1 = 0;\n        if (lap > l2 + 1) return 0;\n      }\n      if (i2 == l2) break;\n    }\n\n    laps.set(lap, i, 0);\n    jump.set(i1, i, 0);\n  }\n\n  let bound = Math.floor(l1 * n1 / l2);\n  let maxPow = 0\n  for (j = 2; j <= bound; j <<= 1)  {\n    for (let i = 0; i < l1; i++) {\n      let t = jump.at(i, maxPow);\n      jump.set(jump.at(t, maxPow), i, maxPow+1);\n      laps.set(laps.at(i, maxPow) + laps.at(t, maxPow), i, maxPow+1);\n    }\n    maxPow++;\n  }\n\n  let x = 0;\n  let p = maxPow;\n  let res = 0;\n\n  while (true) {\n    while (p >= 0 && laps.at(x, p) > n1) p--;\n    if (p < 0) break;\n    n1 -= laps.at(x, p);\n    res += 1 << p;\n    x = jump.at(x, p);\n  }\n\n  return Math.floor(res / n2);\n};\n```
['Dynamic Programming', 'Greedy', 'JavaScript']