Longest Palindromic Subsequence | (DP-28)

Problem Statement: Longest Palindromic Subsequence

A palindromic string is a string that is equal to its reverse. For example: “Nitin” is a palindromic string. Now the question states to find the length of the longest palindromic subsequence of a string. It is that palindromic subsequence of the given string with the greatest length. We need to print the length of the longest palindromic subsequence.

Pre-req: Longest Common Subsequence

Examples
Example:

There can be many subsequences like “b”, “ba”,”bbb” but “bbbb” is the subsequence that is a palindrome and has the greatest length.
Practice:

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Tabulation Approach Space Optimization

Expand any one approach by clicking the given options in the bar. Clicking one approach on bar, closes all other expands. You can manually expand more than one approach at a time

Tabulation Approach
Algorithm / Intuition

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 ( 2n ) 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.

Intuition:

Let us say that we are given the following string.

The longest palindromic subsequence will be: “babcbab”.

What is special 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 please think about 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:

The longest palindromic subsequence of a string is the longest common subsequence of the given string and its reverse.

Approach:

The algorithm is stated as follows:

  • 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 dp-25.
Code

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

// Function to calculate the length of the Longest Common Subsequence
int lcs(string s1, string s2) {
    int n = s1.size();
    int m = s2.size();

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

    // Initialize the 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 the length of the LCS
    return dp[n][m];
}

// Function to calculate the length of the Longest Palindromic Subsequence
int longestPalindromeSubsequence(string s) {
    // Create 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";

    // Call the longestPalindromeSubsequence function and print the result
    cout << "The Length of Longest Palindromic Subsequence is " << longestPalindromeSubsequence(s);
    return 0;
}



import java.util.*;

class TUF {
    // Function to find the length of the Longest Common Subsequence (LCS)
    static int lcs(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();

        // Create a 2D array to store the LCS lengths
        int dp[][] = new int[n + 1][m + 1];
        
        // Initialize the dp array with -1
        for (int rows[] : dp)
            Arrays.fill(rows, -1);

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

        // Fill the dp array using a bottom-up approach
        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]);
            }
        }

        return dp[n][m];
    }

    // Function to find the length of the Longest Palindromic Subsequence
    static int longestPalindromeSubsequence(String s) {
        // Create a reversed version of the input string
        String reversed = new StringBuilder(s).reverse().toString();
        
        // Calculate the LCS of the original string and its reverse
        return lcs(s, reversed);
    }

    public static void main(String args[]) {
        String s = "bbabcbcab";

        System.out.print("The Length of Longest Palindromic Subsequence is ");
        System.out.println(longestPalindromeSubsequence(s));
    }
}


def lcs(s1, s2):
    n = len(s1)
    m = len(s2)

    # Initialize a 2D array to store the length of the LCS
    dp = [[-1] * (m + 1) for i in range(n + 1)]

    # Initialize the first row and first column with 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 using dynamic programming
    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 final value in dp will be the length of the LCS
    return dp[n][m]

def longestPalindromeSubsequence(s):
    # Reverse the input string
    t = s
    s = s[::-1]

    # Find the longest common subsequence between s and its reverse
    return lcs(s, t)

def main():
    s = "bbabcbcab"

    # Calculate and print the length of the longest palindromic subsequence
    print("The Length of Longest Palindromic Subsequence is", longestPalindromeSubsequence(s))

if __name__ == "__main__":
    main()


function lcs(s1, s2) {
    // Get the lengths of the input strings
    const n = s1.length;
    const m = s2.length;

    // Create a 2D array to store the dynamic programming values
    const dp = new Array(n + 1).fill(null).map(() => new Array(m + 1).fill(-1));

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

    // Fill the dp array using dynamic programming
    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]);
            }
        }
    }

    // Return the length of the LCS
    return dp[n][m];
}

// Function to find the length of the Longest Palindromic Subsequence of a string
function longestPalindromeSubsequence(s) {
    // Create a copy of the input string and reverse it
    const t = s.split('').reverse().join('');

    // Find the LCS between the original and reversed strings
    return lcs(s, t);
}

// Main function
function main() {
    const s = "bbabcbcab";
    
    // Call the longestPalindromeSubsequence function and print the result
    console.log("The Length of Longest Palindromic Subsequence is " + longestPalindromeSubsequence(s));
}

// Call the main function to start the program
main();

Output: The Length of Longest Palindromic Subsequence is 7

Complexity Analysis

Time Complexity: O(N*N)

Reason: There are two nested loops

Space Complexity: O(N*N)

Reason: We are using an external array of size ‘(N*N)’. Stack Space is eliminated.

Space Optimization Approach
Algorithm / Intuition

If we closely we are using two rows: dp[ind1-1][ ], dp[ind][ ],

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 and after the inner loop executes, we will set prev = cur, so that the cur row can serve as prev for the next index.

Code

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

// Function to calculate the length of the Longest Common 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 the current values
        prev = cur;
    }

    // The value at prev[m] contains the length of the LCS
    return prev[m];
}

// Function to calculate the length of the Longest Palindromic Subsequence
int longestPalindromeSubsequence(string s) {
    // Create 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";

    // Call the longestPalindromeSubsequence function and print the result
    cout << "The Length of Longest Palindromic Subsequence is " << longestPalindromeSubsequence(s);
    return 0;
}


import java.util.*;

class TUF {
    // Function to find the length of the Longest Common Subsequence (LCS)
    static int lcs(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();

        // Create two arrays to store the LCS lengths
        int[] prev = new int[m + 1];
        int[] cur = new int[m + 1];

        // Base Case: Initialized to 0, as no characters matched yet.

        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 prev array to store the current values
            prev = cur.clone();
        }

        return prev[m];
    }

    // Function to find the length of the Longest Palindromic Subsequence
    static int longestPalindromeSubsequence(String s) {
        // Create a reversed version of the input string
        String reversed = new StringBuilder(s).reverse().toString();

        // Calculate the LCS of the original string and its reverse
        return lcs(s, reversed);
    }

    public static void main(String args[]) {
        String s = "bbabcbcab";

        System.out.print("The Length of Longest Palindromic Subsequence is ");
        System.out.println(longestPalindromeSubsequence(s));
    }
}


def lcs(s1, s2):
    n = len(s1)
    m = len(s2)

    # Initialize two lists, prev and cur, for dynamic programming
    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])
        prev = cur[:]  # Update prev to be a copy of cur for the next iteration

    # The final value in prev will be the length of the LCS
    return prev[m]


def longestPalindromeSubsequence(s):
    # Reverse the input string
    t = s[::-1]

    # Find the length of the longest common subsequence between s and its reverse
    return lcs(s, t)


def main():
    s = "bbabcbcab"

    # Calculate and print the length of the longest palindromic subsequence
    print("The Length of Longest Palindromic Subsequence is", longestPalindromeSubsequence(s))


if __name__ == "__main__":
    main()


function lcs(s1, s2) {
    // Get the lengths of the input strings
    const n = s1.length;
    const m = s2.length;

    // Create two arrays, prev and cur, to store dynamic programming values
    let prev = new Array(m + 1).fill(0);
    let cur = new Array(m + 1).fill(0);

    // Base case is covered as we have initialized prev and cur to 0.

    // Fill the cur array using dynamic programming
    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 prev array with the values from cur for the next iteration
        prev = [...cur];
    }

    // Return the length of the LCS
    return prev[m];
}

// Function to find the length of the Longest Palindromic Subsequence of a string
function longestPalindromeSubsequence(s) {
    // Create a copy of the input string and reverse it
    const t = s.split('').reverse().join('');

    // Find the LCS between the original and reversed strings
    return lcs(s, t);
}

// Main function
function main() {
    const s = "bbabcbcab";

    // Call the longestPalindromeSubsequence function and print the result
    console.log("The Length of Longest Palindromic Subsequence is " + longestPalindromeSubsequence(s));
}

// Call the main function to start the program
main();

Output: The Length of Longest Palindromic Subsequence is 7

Complexity Analysis

Time Complexity: O(N*N)

Reason: There are two nested loops.

Space Complexity: O(N)

Reason: We are using an external array of size ‘N+1’ to store only two rows.

Video Explanation

Special thanks to Anshuman Sharma and Abhipsita Das for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article