Longest palindromic subsequence

We are given a string S, the simplest approach will be to generate all the subsequences and store them, then manually find out the longest palindromic subsequence. This naive approach will give us the correct answer but to generate all the subsequences, we will require exponential ( 2ⁿ ) time. Therefore we will try some other approaches.

Using Dynamic Programming:

We can use the approach discussed in the article Longest Common Subsequence, to find the Longest Palindromic Subsequence.

Understanding:

Let us say that we are given the following string:

The longest palindromic subsequence will be: “babcbab”. The special thing about this string is that it is palindromic (equal to its reverse) and of the longest length.

Now let us write the reverse of 'str' next to it and focus on the highlighted characters. If we look closely at the highlighted characters, they are nothing but the longest common subsequence of the two strings.

Now, we have taken the reverse of the string for the following two reasons:

The longest palindromic subsequence being a palindrome will remain the same when the entire string is reversed.
The length of the palindromic subsequence will also remain the same when the entire string is reversed.

From the above discussion we can conclude that the longest palindromic subsequence of a string is the longest common subsequence of the given string and its reverse.

Approach:

We are given a string (say s), make a copy of it and store it( say string t).
Reverse the original string s.
Find the longest common subsequence as discussed in Longest Common Subsequence.

#include <bits/stdc++.h>
using namespace std;

class Solution{
private:
    /* Function to calculate the length of 
    the Longest Palindromic Subsequence*/
    int func(string s1, string s2) {
        int n = s1.size();
        int m = s2.size();

        // Declare a 2D DP array to store length of the LCS
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, -1));

        // Initialize first row and first column to 0
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 0;
        }
        for (int i = 0; i <= m; i++) {
            dp[0][i] = 0;
        }

        // Fill in the DP array
        for (int ind1 = 1; ind1 <= n; ind1++) {
            for (int ind2 = 1; ind2 <= m; ind2++) {
                if (s1[ind1 - 1] == s2[ind2 - 1])
                    dp[ind1][ind2] = 1 + dp[ind1 - 1][ind2 - 1];
                else
                    dp[ind1][ind2] = max(dp[ind1 - 1][ind2], dp[ind1][ind2 - 1]);
            }
        }
        // The value at dp[n][m] contains length of the LCS
        return dp[n][m];
    }
public:
    /* Function to calculate the length of 
    the Longest Palindromic Subsequence*/
    int longestPalinSubseq(string s){
        // Store a reversed copy of the string
        string t = s;
        reverse(s.begin(), s.end());

        /* Call the LCS function to find the 
        length of the Longest Common Subsequence*/
        return lcs(s, t);
    }
};
int main() {
    string s = "bbabcbcab";
    
    //Create an instance of Solution class
    Solution sol;
    
    // Print the result
    cout << "The Length of Longest Palindromic Subsequence is " << sol.longestPalinSubseq(s);
    return 0;
}


import java.util.*;

class Solution {
    /* Function to calculate the length of 
    the Longest Palindromic Subsequence */
    private int func(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();

        // Declare a 2D DP array to store length of the LCS
        int[][] dp = new int[n + 1][m + 1];

        // Initialize first row and first column to 0
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 0;
        }
        for (int i = 0; i <= m; i++) {
            dp[0][i] = 0;
        }

        // Fill in the DP array
        for (int ind1 = 1; ind1 <= n; ind1++) {
            for (int ind2 = 1; ind2 <= m; ind2++) {
                if (s1.charAt(ind1 - 1) == s2.charAt(ind2 - 1)) {
                    dp[ind1][ind2] = 1 + dp[ind1 - 1][ind2 - 1];
                } else {
                    dp[ind1][ind2] = Math.max(dp[ind1 - 1][ind2], dp[ind1][ind2 - 1]);
                }
            }
        }
        // The value at dp[n][m] contains length of the LCS
        return dp[n][m];
    }

    /* Function to calculate the length of 
    the Longest Palindromic Subsequence */
    public int longestPalinSubseq(String s) {
        // Store a reversed copy of the string
        String t = new StringBuilder(s).reverse().toString();

        /* Call the LCS function to find the 
        length of the Longest Common Subsequence */
        return func(s, t);
    }

    public static void main(String[] args) {
        String s = "bbabcbcab";
        
        // Create an instance of Solution class
        Solution sol = new Solution();
        
        // Print the result
        System.out.println("The Length of Longest Palindromic Subsequence is " + sol.longestPalinSubseq(s));
    }
}
class Solution:
    """ Function to calculate the length of 
    the Longest Palindromic Subsequence """
    def func(self, s1, s2):
        n = len(s1)
        m = len(s2)

        # Declare a 2D DP array to store length of the LCS
        dp = [[0] * (m + 1) for _ in range(n + 1)]

        # Initialize first row and first column to 0
        for i in range(n + 1):
            dp[i][0] = 0
        for i in range(m + 1):
            dp[0][i] = 0

        # Fill in the DP array
        for ind1 in range(1, n + 1):
            for ind2 in range(1, m + 1):
                if s1[ind1 - 1] == s2[ind2 - 1]:
                    dp[ind1][ind2] = 1 + dp[ind1 - 1][ind2 - 1]
                else:
                    dp[ind1][ind2] = max(dp[ind1 - 1][ind2], dp[ind1][ind2 - 1])
        
        # The value at dp[n][m] contains length of the LCS
        return dp[n][m]

    """ Function to calculate the length of 
    the Longest Palindromic Subsequence """
    def longestPalinSubseq(self, s):
        # Store a reversed copy of the string
        t = s[::-1]

        """ Call the LCS function to find the 
        length of the Longest Common Subsequence """
        return self.func(s, t)

if __name__ == "__main__":
    s = "bbabcbcab"
    
    # Create an instance of Solution class
    sol = Solution()
    
    # Print the result
    print("The Length of Longest Palindromic Subsequence is", sol.longestPalinSubseq(s))
class Solution {
    /* Function to calculate the length of 
    the Longest Palindromic Subsequence */
    func(s1, s2) {
        const n = s1.length;
        const m = s2.length;

        // Declare a 2D DP array to store length of the LCS
        const dp = Array.from({ length: n + 1 }, () => Array(m + 1).fill(0));

        // Initialize first row and first column to 0
        for (let i = 0; i <= n; i++) {
            dp[i][0] = 0;
        }
        for (let i = 0; i <= m; i++) {
            dp[0][i] = 0;
        }

        // Fill in the DP array
        for (let ind1 = 1; ind1 <= n; ind1++) {
            for (let ind2 = 1; ind2 <= m; ind2++) {
                if (s1[ind1 - 1] === s2[ind2 - 1]) {
                    dp[ind1][ind2] = 1 + dp[ind1 - 1][ind2 - 1];
                } else {
                    dp[ind1][ind2] = Math.max(dp[ind1 - 1][ind2], dp[ind1][ind2 - 1]);
                }
            }
        }
        // The value at dp[n][m] contains length of the LCS
        return dp[n][m];
    }

    /* Function to calculate the length of 
    the Longest Palindromic Subsequence */
    longestPalinSubseq(s) {
        // Store a reversed copy of the string
        const t = s.split('').reverse().join('');

        /* Call the LCS function to find the 
        length of the Longest Common Subsequence */
        return this.func(s, t);
    }
}

// Main function to test the solution
const s = "bbabcbcab";

// Create an instance of Solution class
const sol = new Solution();

// Print the result
console.log("The Length of Longest Palindromic Subsequence is " + sol.longestPalinSubseq(s));

Complexity Analysis:

Time Complexity: O(N*N), Where N is the length of the given string. Two nested loops are used in order to solve this problem.

Space Complexity: O(N*N), We are using an external array of size ‘(N*N)’.

If we observe the relations obtained in tabultaion approach, dp[ind1 - 1][ind2], dp[ind1][ind2 - 1]. We are using just two rows, dp[ind1-1][ ], dp[ind][ ], in order to calculate the present row.

So we are not required to contain an entire array, we can simply have two rows 'prev' and 'cur' where prev corresponds to dp[ind-1] and cur to dp[ind].

After declaring 'prev' and 'cur', replace dp[ind-1] to prev and dp[ind] with cur in the tabulation code. Following the same logic of tabulation, we will calculate cur[ind] in each iteration and after the inner loop executes, we will set prev = cur, so that the cur row can serve as prev for the next index.

After end of the execution, return prev[n] (n is the length of the string), as our answer, as it will hold the cumulative result of the overall calculation.

#include <bits/stdc++.h>
using namespace std;

class Solution{
private:
    /* Function to calculate the length of 
    the Longest Palindromic Subsequence*/
    int lcs(string s1, string s2) {
        int n = s1.size();
        int m = s2.size();

        /* Create two arrays to store the 
        previous and current rows of DP values*/
        vector<int> prev(m + 1, 0), cur(m + 1, 0);

        /* Base Case is covered as we have
        initialized the prev and cur to 0.*/

        for (int ind1 = 1; ind1 <= n; ind1++) {
            for (int ind2 = 1; ind2 <= m; ind2++) {
                if (s1[ind1 - 1] == s2[ind2 - 1])
                    cur[ind2] = 1 + prev[ind2 - 1];
                else
                    cur[ind2] = max(prev[ind2], cur[ind2 - 1]);
            }
            // Update the prev array with current values
            prev = cur;
        }
        // The value at prev[m] contains length of LCS
        return prev[m];
    }
public:
    /* Function to calculate the length of 
    the Longest Palindromic Subsequence*/
    int longestPalinSubseq(string s){
        // Store a reversed copy of the string
        string t = s;
        reverse(s.begin(), s.end());

        /* Call the LCS function to find the 
        length of the Longest Common Subsequence*/
        return lcs(s, t);
    }
};
int main() {
    string s = "bbabcbcab";
    
    //Create an instance of Solution class
    Solution sol;
    
    // Print the result
    cout << "The Length of Longest Palindromic Subsequence is " << sol.longestPalinSubseq(s);
    return 0;
}


import java.util.*;

class Solution {
    /* Function to calculate the length of 
    the Longest Palindromic Subsequence*/
    private int lcs(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();

        /* Create two arrays to store the 
        previous and current rows of DP values */
        int[] prev = new int[m + 1];
        int[] cur = new int[m + 1];

        /* Base Case is covered as we have
        initialized the prev and cur to 0. */

        for (int ind1 = 1; ind1 <= n; ind1++) {
            for (int ind2 = 1; ind2 <= m; ind2++) {
                if (s1.charAt(ind1 - 1) == s2.charAt(ind2 - 1))
                    cur[ind2] = 1 + prev[ind2 - 1];
                else
                    cur[ind2] = Math.max(prev[ind2], cur[ind2 - 1]);
            }
            // Update the prev array with current values
            System.arraycopy(cur, 0, prev, 0, m + 1);
        }
        // The value at prev[m] contains length of LCS
        return prev[m];
    }

    public int longestPalinSubseq(String s) {
        // Store a reversed copy of the string
        String t = new StringBuilder(s).reverse().toString();

        /* Call the LCS function to find the 
        length of the Longest Common Subsequence */
        return lcs(s, t);
    }

    public static void main(String[] args) {
        String s = "bbabcbcab";
        
        // Create an instance of Solution class
        Solution sol = new Solution();
        
        // Print the result
        System.out.println("The Length of Longest Palindromic Subsequence is " + sol.longestPalinSubseq(s));
    }
}
class Solution:
    """ Function to calculate the length of 
    the Longest Palindromic Subsequence"""
    def lcs(self, s1, s2):
        n = len(s1)
        m = len(s2)

        """ Create two arrays to store the 
        previous and current rows of DP values """
        prev = [0] * (m + 1)
        cur = [0] * (m + 1)

        """ Base Case is covered as we have
        initialized the prev and cur to 0. """

        for ind1 in range(1, n + 1):
            for ind2 in range(1, m + 1):
                if s1[ind1 - 1] == s2[ind2 - 1]:
                    cur[ind2] = 1 + prev[ind2 - 1]
                else:
                    cur[ind2] = max(prev[ind2], cur[ind2 - 1])
            """ Update the prev array with current values """
            prev = cur[:]
        
        # The value at prev[m] contains length of LCS
        return prev[m]

    def longestPalinSubseq(self, s):
        # Store a reversed copy of the string
        t = s[::-1]

        """ Call the LCS function to find the 
        length of the Longest Common Subsequence"""
        return self.lcs(s, t)

if __name__ == "__main__":
    s = "bbabcbcab"
    
    # Create an instance of Solution class
    sol = Solution()
    
    # Print the result
    print("The Length of Longest Palindromic Subsequence is", sol.longestPalinSubseq(s))
class Solution {
    /* Function to calculate the length of 
    the Longest Palindromic Subsequence*/
    lcs(s1, s2) {
        const n = s1.length;
        const m = s2.length;

        /* Create two arrays to store the 
        previous and current rows of DP values */
        const prev = new Array(m + 1).fill(0);
        const cur = new Array(m + 1).fill(0);

        /* Base Case is covered as we have
        initialized the prev and cur to 0. */

        for (let ind1 = 1; ind1 <= n; ind1++) {
            for (let ind2 = 1; ind2 <= m; ind2++) {
                if (s1[ind1 - 1] === s2[ind2 - 1])
                    cur[ind2] = 1 + prev[ind2 - 1];
                else
                    cur[ind2] = Math.max(prev[ind2], cur[ind2 - 1]);
            }
            /* Update the prev array with current values */
            for (let k = 0; k <= m; k++) {
                prev[k] = cur[k];
            }
        }
        // The value at prev[m] contains length of LCS
        return prev[m];
    }

    longestPalinSubseq(s) {
        // Store a reversed copy of the string
        const t = s.split('').reverse().join('');

        /* Call the LCS function to find the 
        length of the Longest Common Subsequence */
        return this.lcs(s, t);
    }
}

const s = "bbabcbcab";

// Create an instance of Solution class
const sol = new Solution();

// Print the result
console.log("The Length of Longest Palindromic Subsequence is " + sol.longestPalinSubseq(s));

Complexity Analysis:

Time Complexity: O(N*N), Where N is the length of the given string. Two nested loops are used in order to solve this problem.

Space Complexity: O(N), We are using an external array of size ‘N+1’ to store only two rows.

Problem List

Longest palindromic subsequence

Examples:

Constraints

Hints

Company Tags

Editorial

Using Dynamic Programming:

Understanding:

Approach:

Complexity Analysis:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code