# Memoization and Binary Search solution

• ``````var getMaxRepetitions = function(s1, n1, s2, n2) {

const n = s1.length;

// if s2 contains letters that are not in s1 return 0
if (s2.split('').some(ch => s1.indexOf(ch) === -1))
return 0;

const jump = Array(n);
for (let start = 0; start < n; start++) {
let i = 0, j = 0;
while (j < s2.length) {
if (s1[(start + i) % n] === s2[j])
j++;
i++;
}
jump[start] = i;
}

// how many chars we need in string s1 to find
// count s2 strings starting from index i in s1
const getCharsCount = memoize(function (i, count) {
if (count === 0)
return 0;

if (count % 2 === 1)
return jump[i] + getCharsCount((i + jump[i]) % n, count - 1);

let half = getCharsCount(i, count / 2);
return half + getCharsCount((i + half) % n, count / 2);
});

// binary search for repetetitions count
let from = 0, to = 100000000, charsLimit = s1.length * n1;
while (from <= to) {
const mid = (from + to) >> 1;
if (getCharsCount(0, mid) <= charsLimit)
from = mid + 1;
else
to = mid - 1;
}

return Math.floor((from - 1) / n2);
};

// memoize function for 2 arguments
function memoize (fn) {
const cache = new Map();
return function (arg1, arg2) {
const key = `\${arg1}#\${arg2}`;
if (cache.has(key))
return cache.get(key);
const result = fn(arg1, arg2);
cache.set(key, result);
return result;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.