LeetCode 516. Longest Palindromic Subsequence (javascript solution)

Description:

Given a string s, find the longest palindromic subsequence's length in s.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Solution:

Time Complexity : O(n^2)
Space Complexity: O(n^2)

var longestPalindromeSubseq = function(s) {
    const dp = [...Array(s.length)].map(() => Array(s.length).fill(0))

    // Base case 
    for(let i = 0; i < s.length; i++) {
        dp[i][i] = 1
    }

    for(let i = 1; i < s.length; i++) {
        for(let j = 0; j < s.length; j++){
            if(j+i < s.length){
                // If the end letter and start letter are the same add 2 to the value in the bottom left diagonal. This value is a potential palindrome. If the letters are not equal set the current value to the previous highest palindrome subsequence
                dp[j][j+i] = s[j] === s[j + i] 
                    ? dp[j+1][j+i-1] + 2
                    : Math.max(dp[j][j+i-1], dp[j+1][i+j])
            }
        }
    }

    return dp[0][s.length-1]
};

Comments

[Satyagraha]

*JAVA | SIMPLE EXPLANATION | DETAILED CODE WITH COMMENTS
*

Simple Explanation of Bottom up DP Approach and Space Optimization. In PART 1, we had discussed Top Down DP approach.

youtube.com/watch?v=TqNrPslO8KE

class LongestPalindromicSubsequenceBottomUpDPSolution {
    public int longestPalindromeSubseq(String s) {

        //Length of string
        int n = s.length();

        //Matrix to store results
        int[][] dp = new int[n][n];

        //For length 1 => result is 1 since it is a palindrome
        int i, j;
        for(i=0; i<n; i++) {
            //For length 1, i and j are same
            j=i;
            dp[i][j] = 1;
        }

        //For length 2 => we'll have to check the 2 characters at i and j. If
        //they are equal => result is 2. If they are not equal => result is 1.
        for(i=0; i<n-1; i++) {
            //for length 2, j will be i+1
            j=i+1;
            if(s.charAt(i) == s.charAt(j)) {
                dp[i][j] = 2;
            } else {
                dp[i][j] = 1;
            }
        }

        //For length 3 to n, we'll fix length in first loop. In second loop,
        //we'll fix starting position for that length.
        int length;
        for(length=3; length<=n; length++) {
            //i will go till n-length because j's value will reach equal to n-1
            for(i=0; i<n-length+1; i++) {
                //Example j = 0+3-1 = 2 => relevant part of string is 0 to 2
                j=i+length-1;

                //If the 2 characters are equal => lps of middle portion +2 is
                //answer
                if(s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i+1][j-1] + 2;
                } else {
                    //Else maximum of the 2 candidates is answer. One candidate
                    //is the string without last character. Other candidate
                    //is the string without the first character.
                    dp[i][j] = Math.max(dp[i][j-1], dp[i+1][j]);
                }
            }
        }

        return dp[0][n-1];
    }
}

SPACE OPTIMIZATION CODE

class LongestPalindromicSubsequenceBottomUpSpaceOptimizationSolution {
    public int longestPalindromeSubseq(String s) {

        //Length of string
        int n = s.length();

        if(n==1) return 1;

        //This array will correspond to a particular length of the substring.
        //Every position of this array will correspond to the starting position
        //in the string for this particular length.
        //Every element of thi sarray will correspond to the lps for the combination
        //of starting position and length.
        int[] secondPrevLengthArray = new int[n];
        int[] prevLengthArray = new int[n];

        //Initially, secondPrevLengthArray will correspond to length 1
        //and prevLengthArray will correspond to length 2

        //For length 1 => result is 1 since it is a palindrome
        int i, j;
        for(i=0; i<n; i++) {
            secondPrevLengthArray[i] = 1;
        }

        //For length 2 => we'll check if the 2 characters are same.
        //If they are => result is 2. If they are not => result is 1.
        for(i=0; i<n-1; i++) {
            j = i+1;
            //If the 2 chars are equal => at this starting position and for length 2
            //lps is 2
            if(s.charAt(i) == s.charAt(j)) {
                prevLengthArray[i] = 2;
            } else {
                prevLengthArray[i] = 1;
            }
        }

        //This array will store results for the current length.
        int[] newArr = new int[n];

        //Iterate from length 3 to n
        int length;
        for(length = 3; length<=n; length++) {
            //For this length, let us now fix starting position one by one
            //i will go till n-length because j's value will reach equal to n-1
            for(i=0; i<n-length+1; i++) {
                //Example j = 0+3-1 = 2 => relevant part of string is 0 to 2
                j = i+length-1;

                //If the 2 characters are equal => lps of middle portion +2 is
                //answer. Middle portion's length will be 2 less than current length
                //So, middle portion's answer will lie in secondPrevLengthArray
                if(s.charAt(i) == s.charAt(j)) {
                    newArr[i] = secondPrevLengthArray[i+1] + 2;
                } else {
                    //Else, it'll be max of the 2 candidates. One is lps when
                    //string doesn't take into account last character. One is lps
                    //when string doesn't take into account the first character.
                    //Since only one character is less => candidates will lie in
                    //prevLengthArray
                    newArr[i] = Math.max(prevLengthArray[i], prevLengthArray[i+1]);
                }
            }
            //By now, we'd have filled newArr for particular length. Now, for next
            //iteration, this newArr will become prevLengthArray and the current
            //prevLengthArray will become secondPrevLengthArray. The current
            //secondPrevLengthArray is useless for us now.
            copyArray1ToArray2(prevLengthArray, secondPrevLengthArray, n);
            copyArray1ToArray2(newArr, prevLengthArray, n);

        }

        //At the end, our answer will be in prevLengthArray's first element.
        //Because, that will correspond to full length with starting position as 0
        return prevLengthArray[0];
    }

    private static void copyArray1ToArray2(int[] toBeCopied, int[] toBeCopiedInto, int n) {
        int i;
        for(i=0; i<n; i++) {
            toBeCopiedInto[i] = toBeCopied[i];
        }
    }
}