Optimizing recursive string management with JavaScript

Question

Problem

I was asked this problem in my algorithm class today:

This function maxSubstring(s, t), where sis the string, and tis the substring s, find the maximum number of iterations that you can remove either the first or last occurrence of the substring t.

Concept

Here is a visualization of the function maxSubstringcalled on s = banababbaaand t = ba.

          b  a  n  a  b  b  a  a
1st move: n  a  b  a  b  b  a            or   b  a  n  a  b  a  b  a
2nd move: n a b b a a  or  n a b a b a        n a b a b a  or  b a n a b a
3rd move:    n a b a   or   n a b a             n a b a    or    n a b a
4th move:             n  a                                n  a

Thus, this operation takes four moves.

Attempt

Here is my solution to the problem. It works, but it is very slow when I use larger strings as arguments.

Attempt # 1

function maxSubstring(s, t) {
    if (s.includes(t)) {
        var idxSubstr = s.replace(t, '');
        var lastIdxSubstr = s.substr(0, s.lastIndexOf(t)) + s.substr(s.lastIndexOf(t) + t.length, s.length);
        return 1 + Math.max(maxSubstring(idxSubstr, t), maxSubstring(lastIdxSubstr, t)));
    }
    return 0;
}

Attempt # 2

function maxSubstring(s, t) {
    if (s.includes(t)) {
        var idx = s.indexOf(t), lastIdx = s.lastIndexOf(t);
        var idxSubstr = s.substr(0, idx) + s.substr(idx + t.length, s.length);
        var lastIdxSubstr = s.substr(0, lastIdx) + s.substr(lastIdx + t.length, s.length);
        if (idx != lastIdx) {
            return 1 + Math.max(maxSubstring(idxSubstr, t), maxSubstring(lastIdxSubstr, t));
        } else {
            return 1 + maxSubstring(idxSubstr, t);
        }
    }
    return 0;
}

The reason for the update: a slight change in efficiency by storing values indexOfand lastIndexOfvariables.

# 3

function maxSubstring(s, t) {
    var idx = s.indexOf(t);
    if (idx >= 0) {
        var lastIdx = s.lastIndexOf(t);
        var idxSubstr = s.substr(0, idx) + s.substr(idx + t.length);
        if (idx != lastIdx) {
            var lastIdxSubstr = s.substr(0, lastIdx) + s.substr(lastIdx + t.length);
            return 1 + Math.max(maxSubstring(idxSubstr, t), maxSubstring(lastIdxSubstr, t));
        } else {
            return 1 + maxSubstring(idxSubstr, t);
        }
    }
    return 0;
}

: , lastIndexOf , .

- , ? Math.max , , - , .

, maxSubstring , Math.max , ( ).

, , Big O Notation Big O Notation ? , , . .

Answer 1

, , , s - , .

- memoisation - .

, , - , . , , . , . maxSubstring('ababaa', 'aba').

function maxSubstring(s, t, prevResults = new Map()) {
    function result(x) { prevResults.set(s, x); return x; }
    if (prevResults.has(s))
        return prevResults.get(s); // memoisation

    const first = s.indexOf(t);
    if (first == -1)
        return result(0);
    const withoutFirst = s.slice(0, first) + s.slice(first + t.length);

    const last = s.lastIndexOf(t);
    if (last == first) // only one match
        return result(1 + maxSubstring(withoutFirst, t, prevResults));

    if (t.lastIndexOf(t.charAt(t.length-1), t.length-1) == -1 // last character of t is found nowhere else in t
        || !t.includes(s.charAt(first+t.length))) // character after the match can never be part of a match
        // so this match is always removed in the optimal sequence and it doesn't matter whether as first or last
        return result(1 + maxSubstring(withoutFirst, t, prevResults));

    const withoutLast = s.slice(0, last) + s.slice(last + t.length);
    if (t.indexOf(t.charAt(0), 1) == -1 // first character of t is found nowhere else in t
        || !t.includes(s.charAt(last - 1))) // character before the match can never be part of a match
        // so this match is always removed and it doesn't matter when
        return result(1 + maxSubstring(withoutLast, t, prevResults));

    return result(1 + Math.max(maxSubstring(withoutFirst, t, prevResults),
                               maxSubstring(withoutLast, t, prevResults)));
}

. ( ).

(indexOf, slice ..) Map, , . , .