Optimize recursive string manipulation function with JavaScript

Question

Problem

I was given this problem in my Algorithms class today:

Given function maxSubstring(s, t), where s is a string and t is a substring of s, find the maximum number of iterations you can delete either the first or last occurrence of substring t .

Concept

Here is a visualization of the function maxSubstring called on s = banababbaa and 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;
}

Reason for update: Minor change in efficiency by storing values of indexOf and lastIndexOf in variables.

Attempt #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;
}

Reason for update: Reduced instances in which certain values were redefined and prevented lastIndexOf calculation before the first index is checked.

Answer Requirements

Is there any algorithm or method I may use to optimize this code? Math.max is the main culprit, so I would appreciate it if anyone has an idea on how to avoid using this method altogether.

In other words, maxSubstring should only be called once inside of itself, but Math.max requires that it be called twice (once for the first index of a substring and another time for the last index of that substring).

Lastly, do you mind telling me what the Big O Notation is for my solution and what the Big O Notation is for yours? This is not part of the original challenge, but I am curious, myself. Thanks in advance.

Answer 1

The major problem with the naive recursive algorithm that you have presented is that it is called very often on the same input s - exponentially often even, and exactly that is what causes the noticeable slowdown on larger strings.

What you can do against this is to use memoisation - remember the result for a specific input in a lookup table.

Another optimisation you can do is check whether deleting the first vs the last lead to different results at all. In most cases, it will absolutely not matter in which sequence you remove them, the number of possible removals is always the same. However, that is not the case when the matched substring can overlap with itself. As an example, try 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)));
}

Time Complexity Analysis

The number of recursive calls should be roughly quadratic in the number of removals. With my second suggestion, it might get down to linear in the best cases (depending on the patterns).

For every call, factor in the linear searches (indexOf, slice, etc.) and the Map lookup, though their average complexity will be less than that as the input get smaller and the pattern is often found early in the input. In any case, the complexity is polynomial, not exponential.