Articles by FavTutor
  • AI News
  • Data Structures
  • Web Developement
  • AI Code GeneratorNEW
  • Student Help
  • Main Website
No Result
View All Result
FavTutor
  • AI News
  • Data Structures
  • Web Developement
  • AI Code GeneratorNEW
  • Student Help
  • Main Website
No Result
View All Result
Articles by FavTutor
No Result
View All Result
Home Data Structures and Algorithms

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

Jatin Chanana by Jatin Chanana
December 6, 2023
Reading Time: 7 mins read
Longest palindromic subsequence
Follow us on Google News   Subscribe to our newsletter

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”.
result of the example
  • 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.

ShareTweetShareSendSend
Jatin Chanana

Jatin Chanana

I am Jatin, a final-year undergraduate student with a keen interest in the field of software development. I possess a strong academic background and a deep passion for Data Structures, Algorithms, and Web Development.

RelatedPosts

validate ip address

Validate IP Address Problem ( C++, JAVA, Python)

April 3, 2025
Shortest Palindrome Problem

Shortest Palindrome Problem ( C++, JAVA, Python)

April 4, 2025
Zigzag Conversion Problem

Zigzag Conversion Problem (C++, Java, Python)

April 4, 2025
Next Right Pointers In Each Node

Populating Next Right Pointers In Each Node (with code)

March 27, 2024
Coin Change II

Coin Change II Problem (C++, Java, Python)

April 7, 2025

About FavTutor

FavTutor is a trusted online tutoring service to connects students with expert tutors to provide guidance on Computer Science subjects like Java, Python, C, C++, SQL, Data Science, Statistics, etc.

Categories

  • AI News, Research & Latest Updates
  • Trending
  • Data Structures
  • Web Developement
  • Data Science

Important Subjects

  • Python Assignment Help
  • C++ Help
  • R Programming Help
  • Java Homework Help
  • Programming Help

Resources

  • About Us
  • Contact Us
  • Editorial Policy
  • Privacy Policy
  • Terms and Conditions

Website listed on Ecomswap. © Copyright 2025 All Rights Reserved.

No Result
View All Result
  • AI News
  • Data Structures
  • Web Developement
  • AI Code Generator
  • Student Help
  • Main Website

Website listed on Ecomswap. © Copyright 2025 All Rights Reserved.