JavaScript algorithm to check for Palindrome by deleting at most one character - time complexity for this recursive approach

user_7624223 0
Viewed 195

Here is the leetcode question where you are given a string s and you can delete at most one character to judge whether or not this is a palindrome. For example,

Input: "abca"
Output: True
Explanation: You could delete the character 'c'.

So here is my solution using recursion

var validPalindrome = function(s) {
    if(s.trim().length === 0) return true
    
    const isValidPalindrome = (start, end, skipped) => {
        if(skipped > 1) return false
        if(start >= end) return true
        if(s[start] === s[end]) return isValidPalindrome(start+1,end-1, skipped)
        else return isValidPalindrome(start, end - 1, skipped + 1) || isValidPalindrome(start + 1, end, skipped + 1)
    }
    
    return isValidPalindrome(0, s.length - 1, 0)
};

When there's a mismatch between the left character and the right character, you can skip one or the other, but you don't know which one. Therefore, at this point, you simply need to explore both of these paths.

But I am having a hard time analyzing the time complexity for this type of recursion. I know that the iterative version of this solution should have an O(n) runtime. Not sure how I can approach analyzing the time complexity here.

big-o algorithm javascript
1 Answers

In all of the recursive calls, start gets increased and/or end gets decreased. The recursion stops when start >= end. Therefore in the worst possible case when only start or end changes at each iteration, it will recurse end - start = n times.

As you already observed, the two recursive calls could be a problem, but as skipped gets increased, and recursion stops when skipped > 1, this path will only be taken once. As such we could rewrite the code into two functions, with the second one being:

     const isValidPalindromeTailRecursion = (start, end) => {
       if(start >= end) return true
       if(s[start] === s[end]) return isValidPalindrome(start+1,end-1, skipped)
       else return false;
    };

Now determining the time complexity of this version is easy as we only have tail recursion:

 T(1) = 1
 T(n) = T(n - 1) + 1 = n

Given that, we can take the original function and rewrite it:

     const isValidPalindrome = (start, end) => {     
       if(start >= end) return true
       if(s[start] === s[end]) return isValidPalindrome(start+1,end-1)
       else return isValidPalindromeTailRecursion(start, end - 1) || isValidPalindromeTailRecursion(start + 1, end)
    }

Now analyzing this one is way simpler, let's look at three cases:

1.) There is a valid palindrome:

isValidPalindrome recurses through the string, increasing start and decreasing end each step. Therefore there will be n / 2 recursive steps. In this case the time complexity is O(n).

2.) There is no palindrome, and only the m'th character is different:

isValidPalindrome recurses m times, till it find's the different character. From there on isValidPalindromeTailRecursion gets called twice, and recurses till the end (n - m steps). In total there are m + 2 * (n - m) steps, resulting in a time complexity of O(n).

3.) There is no palindrome, and multiple characters are different:

Just as in 2.) isValidPalindrome recurses m times till the first difference is found, then isValidPalindromeTailRecursion recurses twice, till the second difference is found, at that point the algorithm terminates. In total there are m + 2 * (m² - m) steps (where m² is the place of the second occurence). As m, m² < n, this also results in a time complexity of O(n).

As such, this algorithm is O(n) overall.

user_52600240
Related