Longest Palindromic Subsequence ( C++, Java, Python )

In string manipulation and pattern recognition, one of the famous problems is finding the Longest Palindromic Subsequence within a given string. As we know, a palindromic subsequence is a sequence of characters that reads the same forwards and backward. In this article, we will understand this problem and discuss an optimal approach using dynamic programming to solve this problem.

Longest Palindromic Subsequence Problem

In this LPS problem, we are given a string S and we have to find the length of the Longest Palindromic Subsequence. The Longest Palindromic Subsequence refers to the maximum-length subsequence of the string that is also a palindrome.

A subsequence is a sequence of characters obtained from the original sequence and their order is preserved, but not necessarily all characters need to be included.

Let us understand this problem with an example:

String = “favtutor”
Output = 3

One possible longest palindromic subsequence is “tut”. As we can see if we read it backward it’s the same.

Example of Longest palindromic subsequence

Dynamic Programming to Find LPS

The longest sequence of letters reads the same backward as forward. Now, if you reverse the entire original string, the longest palindromic subsequence will still be a palindrome (reads the same backward and forward), and its length will stay the same. It’s like a property that these palindromic things maintain even when we reverse it.

String = “favtutor”
Reversed_string = “rotutvaf”

Steps to solve using DP:

Create a dp (dynamic programming) array of size [n][m], where n and m are the lengths of String and reversed_string, respectively. This array will store the result of every subproblem until it does not occur again.
We will initialize the dp array with -1 because none of the subproblems is solved in the beginning.
we will find the answer for particular indices (e.g., LCS (ind1, ind2)), and if s1[i] == s2[j] we will do i = i-1, j = j-1. Otherwise we will try (i,j-1) or (i-1,j).

Steps to solve LPS using Dynamic Programming

string[i]==reversed_string[j] is equal in case of “tut”.

We first check whether the answer has already been calculated using the dp array (i.e., dp[ind1][ind2] != -1). If it has, we simply return the value from the dp[ind1][ind2].
If the answer has not been calculated yet, we will use the recursive relation as usual. However, before returning from the function, we set dp[ind1][ind2] to the solution we obtained.

C++ Code

Here is the C++ program to solve the LPS problem using dynamic programming:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int longestPalindromeSubseqHelper(string &s, string &t, int i, int j, vector<vector<int>> &dp) {
    // Base case: if the substring has one or zero characters, it's a palindrome
    if (i >= s.length() || j >= t.length()) {
        return 0;
    }

    // Check if the result is already computed
    if (dp[i][j] != -1) {
        return dp[i][j];
    }

    // If the characters at the current positions match, extend the palindrome
    if (s[i] == t[j]) {
        dp[i][j] = 1 + longestPalindromeSubseqHelper(s, t, i + 1, j + 1, dp);
    } else {
        // If the characters don't match, take the maximum of excluding either
        // the last character from the beginning or the last character from the end
        dp[i][j] = max(longestPalindromeSubseqHelper(s, t, i + 1, j, dp),
                       longestPalindromeSubseqHelper(s, t, i, j + 1, dp));
    }

    return dp[i][j];
}

int longestPalindromeSubseq(string s) {
    // Create a reversed copy of the input string
    string t = s;
    reverse(t.begin(), t.end());

    // Create a 2D array for dynamic programming and initialize with -1
    vector<vector<int>> dp(s.length(), vector<int>(t.length(), -1));

    // Call the helper function to compute the result
    return longestPalindromeSubseqHelper(s, t, 0, 0, dp);
}

int main() {
    string s = "favtutor";
    int result = longestPalindromeSubseq(s);

    cout << "The length of the longest palindromic subsequence in '" << s << "' is: " << result << endl;

    return 0;
}

Java Code

You can also implement it in Java as well:

import java.util.Arrays;

public class LongestPalindromicSubsequence {

    static int longestPalindromeSubseqHelper(String s, String t, int i, int j, int[][] dp) {
        // Base case: if the substring has one or zero characters, it's a palindrome
        if (i >= s.length() || j >= t.length()) {
            return 0;
        }

        // Check if the result is already computed
        if (dp[i][j] != -1) {
            return dp[i][j];
        }

        // If the characters at the current positions match, extend the palindrome
        if (s.charAt(i) == t.charAt(j)) {
            dp[i][j] = 1 + longestPalindromeSubseqHelper(s, t, i + 1, j + 1, dp);
        } else {
            // If the characters don't match, take the maximum of excluding either
            // the last character from the beginning or the last character from the end
            dp[i][j] = Math.max(longestPalindromeSubseqHelper(s, t, i + 1, j, dp),
                                longestPalindromeSubseqHelper(s, t, i, j + 1, dp));
        }

        return dp[i][j];
    }

    static int longestPalindromeSubseq(String s) {
        // Create a reversed copy of the input string
        StringBuilder reversed = new StringBuilder(s).reverse();
        String t = reversed.toString();

        // Create a 2D array for dynamic programming and initialize with -1
        int[][] dp = new int[s.length()][t.length()];
        for (int[] row : dp) {
            Arrays.fill(row, -1);
        }

        // Call the helper function to compute the result
        return longestPalindromeSubseqHelper(s, t, 0, 0, dp);
    }

    public static void main(String[] args) {
        String s = "favtutor";
        int result = longestPalindromeSubseq(s);
        System.out.println("The length of the longest palindromic subsequence in '" + s + "' is: " + result);
    }
}

Python Code

Below is the Python program for this approach:

def longestPalindromeSubseqHelper(s, t, i, j, dp):
    # Base case: if the substring has one or zero characters, it's a palindrome
    if i >= len(s) or j >= len(t):
        return 0

    # Check if the result is already computed
    if dp[i][j] != -1:
        return dp[i][j]

    # If the characters at the current positions match, extend the palindrome
    if s[i] == t[j]:
        dp[i][j] = 1 + longestPalindromeSubseqHelper(s, t, i + 1, j + 1, dp)
    else:
        # If the characters don't match, take the maximum of excluding either
        # the last character from the beginning or the last character from the end
        dp[i][j] = max(longestPalindromeSubseqHelper(s, t, i + 1, j, dp),
                       longestPalindromeSubseqHelper(s, t, i, j + 1, dp))

    return dp[i][j]

def longestPalindromeSubseq(s):
    # Create a reversed copy of the input string
    t = s[::-1]

    # Create a 2D array for dynamic programming and initialize with -1
    dp = [[-1 for _ in range(len(t))] for _ in range(len(s))]

    # Call the helper function to compute the result
    return longestPalindromeSubseqHelper(s, t, 0, 0, dp)

# Main function
s = "favtutor"
result = longestPalindromeSubseq(s)
print(f"The length of the longest palindromic subsequence in '{s}' is: {result}")

Output:

The length of the longest palindromic subsequence in 'favtutor' is: 3

Complexity Analysis

The time complexity is determined by the number of subproblems that need to be solved. In this case, there are O(m*n) subproblems, where m is the length of the first string (s1) and n is the length of the reversed_string.

The space complexity is determined by the memory required for the memoization table (dp). The table is a 2D array of size (m+1)*(n+1), where m is the length of s1 and n is the length of reversed_string. So overall space complexity is O(m*n).

Conclusion

This article explores the Longest palindromic Subsequence (LPS) problem, which involves finding the length of the longest palindromic subsequence in a string. Using the intuition that the longest common subsequence between a string and its reversed_string is the longest palindromic subsequence, we can easily solve this problem using dynamic programming.