Memoization and Binary Search solution


  • 0
    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;
        }
    }
    

Log in to reply
 

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