Given a string āSā, find the length of the Longest Palindromic Subsequence in it.
The Longest Palindromic Subsequence (LPS) is the problem of finding a maximum-length subsequence of a given string that is also a Palindrome.
Longest Palindromic Subsequence
Examples:
Input: S = āGEEKSFORGEEKSā
Output: 5
Explanation: The longest palindromic subsequence we can get is of length 5. There are more than 1 palindromic subsequences of length 5, for example: EEKEE, EESEE, EEFEE, ā¦etc.Input: S = āBBABCBCABā
Output: 7
Explanation: As āBABCBABā is the longest palindromic subsequence in it. āBBBBBā and āBBCBBā are also palindromic subsequences of the given sequence, but not the longest ones.
Recursive solution to find the Longest Palindromic Subsequence (LPS):
The naive solution for this problem is to generate all subsequences of the given sequence and find the longest palindromic subsequence. This solution is exponential in terms of time complexity. Let us see how this problem possesses both important properties of a Dynamic Programming (DP) Problem and can efficiently be solved using Dynamic Programming.
Following is a general recursive solution with all cases handled.Ā
- Case1: Every single character is a palindrome of length 1
- L(i, i) = 1 (for all indexes i in given sequence)
- Case2: If first and last characters are not same
- If (X[i] != X[j]) Ā L(i, j) = max{L(i + 1, j), L(i, j ā 1)}Ā
- Case3: If there are only 2 characters and both are same
- Else if (j == i + 1) L(i, j) = 2 Ā
- Case4: If there are more than two characters, and first and last characters are same
- Else L(i, j) = Ā L(i + 1, j ā 1) + 2Ā
Below is the implementation for the above approach:
C++
// C++ program of above approach#include <bits/stdc++.h>using namespace std;Ā
// A utility function to get max// of two integersint max(int x, int y) { return (x > y) ? x : y; }Ā
// Returns the length of the longest// palindromic subsequence in seqint lps(char* seq, int i, int j){Ā
Ā Ā Ā Ā // Base Case 1: If there isĀ Ā Ā Ā // only 1 characterĀ Ā Ā Ā if (i == j)Ā Ā Ā Ā Ā Ā Ā Ā return 1;Ā
Ā Ā Ā Ā // Base Case 2: If there are only 2Ā Ā Ā Ā // characters and both are sameĀ Ā Ā Ā if (seq[i] == seq[j] && i + 1 == j)Ā Ā Ā Ā Ā Ā Ā Ā return 2;Ā
Ā Ā Ā Ā // If the first and last characters matchĀ Ā Ā Ā if (seq[i] == seq[j])Ā Ā Ā Ā Ā Ā Ā Ā return lps(seq, i + 1, j - 1) + 2;Ā
Ā Ā Ā Ā // If the first and last charactersĀ Ā Ā Ā // do not matchĀ Ā Ā Ā return max(lps(seq, i, j - 1), lps(seq, i + 1, j));}Ā
// Driver program to test above functionsint main(){Ā Ā Ā Ā char seq[] = "GEEKSFORGEEKS";Ā Ā Ā Ā int n = strlen(seq);Ā Ā Ā Ā cout << "The length of the LPS is "Ā Ā Ā Ā Ā Ā Ā Ā Ā << lps(seq, 0, n - 1);Ā Ā Ā Ā return 0;} |
C
// C program of above approach#include <stdio.h>#include <string.h>Ā
// A utility function to get max of two integersint max(int x, int y) { return (x > y) ? x : y; }Ā
// Returns the length of the longest palindromic subsequence// in seqint lps(char* seq, int i, int j){Ā Ā Ā Ā // Base Case 1: If there is only 1 characterĀ Ā Ā Ā if (i == j)Ā Ā Ā Ā Ā Ā Ā Ā return 1;Ā
Ā Ā Ā Ā // Base Case 2: If there are only 2 characters and bothĀ Ā Ā Ā // are sameĀ Ā Ā Ā if (seq[i] == seq[j] && i + 1 == j)Ā Ā Ā Ā Ā Ā Ā Ā return 2;Ā
Ā Ā Ā Ā // If the first and last characters matchĀ Ā Ā Ā if (seq[i] == seq[j])Ā Ā Ā Ā Ā Ā Ā Ā return lps(seq, i + 1, j - 1) + 2;Ā
Ā Ā Ā Ā // If the first and last characters do not matchĀ Ā Ā Ā return max(lps(seq, i, j - 1), lps(seq, i + 1, j));}Ā
/* Driver program to test above functions */int main(){Ā Ā Ā Ā char seq[] = "GEEKSFORGEEKS";Ā Ā Ā Ā int n = strlen(seq);Ā Ā Ā Ā printf("The length of the LPS is %d",Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā lps(seq, 0, n - 1));Ā Ā Ā Ā getchar();Ā Ā Ā Ā return 0;} |
Java
// Java program of above approachimport java.io.*;import java.util.*;Ā
class GFG {Ā
Ā Ā Ā Ā // A utility function to get max of two integersĀ Ā Ā Ā static int max(int x, int y) { return (x > y) ? x : y; }Ā Ā Ā Ā // Returns the length of the longest palindromicĀ Ā Ā Ā // subsequence in seqĀ
Ā Ā Ā Ā static int lps(char seq[], int i, int j)Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā // Base Case 1: If there is only 1 characterĀ Ā Ā Ā Ā Ā Ā Ā if (i == j) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return 1;Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Base Case 2: If there are only 2 characters andĀ Ā Ā Ā Ā Ā Ā Ā // both are sameĀ Ā Ā Ā Ā Ā Ā Ā if (seq[i] == seq[j] && i + 1 == j) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return 2;Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā // If the first and last characters matchĀ Ā Ā Ā Ā Ā Ā Ā if (seq[i] == seq[j]) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return lps(seq, i + 1, j - 1) + 2;Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā // If the first and last characters do not matchĀ Ā Ā Ā Ā Ā Ā Ā return max(lps(seq, i, j - 1), lps(seq, i + 1, j));Ā Ā Ā Ā }Ā
Ā Ā Ā Ā /* Driver program to test above function */Ā Ā Ā Ā public static void main(String[] args)Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā String seq = "GEEKSFORGEEKS";Ā Ā Ā Ā Ā Ā Ā Ā int n = seq.length();Ā Ā Ā Ā Ā Ā Ā Ā System.out.printf("The length of the LPS is %d",Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā lps(seq.toCharArray(), 0, n - 1));Ā Ā Ā Ā }} |
Python3
# Python 3 program of above approachĀ
# A utility function to get max# of two integersĀ
Ā
def max(x, y):Ā Ā Ā Ā if(x > y):Ā Ā Ā Ā Ā Ā Ā Ā return xĀ Ā Ā Ā return yĀ
# Returns the length of the longest# palindromic subsequence in seqĀ
Ā
def lps(seq, i, j):Ā
Ā Ā Ā Ā # Base Case 1: If there isĀ Ā Ā Ā # only 1 characterĀ Ā Ā Ā if (i == j):Ā Ā Ā Ā Ā Ā Ā Ā return 1Ā
Ā Ā Ā Ā # Base Case 2: If there are only 2Ā Ā Ā Ā # characters and both are sameĀ Ā Ā Ā if (seq[i] == seq[j] and i + 1 == j):Ā Ā Ā Ā Ā Ā Ā Ā return 2Ā
Ā Ā Ā Ā # If the first and last characters matchĀ Ā Ā Ā if (seq[i] == seq[j]):Ā Ā Ā Ā Ā Ā Ā Ā return lps(seq, i + 1, j - 1) + 2Ā
Ā Ā Ā Ā # If the first and last charactersĀ Ā Ā Ā # do not matchĀ Ā Ā Ā return max(lps(seq, i, j - 1),Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā lps(seq, i + 1, j))Ā
Ā
# Driver Codeif __name__ == '__main__':Ā Ā Ā Ā seq = "GEEKSFORGEEKS"Ā Ā Ā Ā n = len(seq)Ā Ā Ā Ā print("The length of the LPS is",Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā lps(seq, 0, n - 1))Ā
# This code contributed by Rajput-Ji |
C#
// C# program of the above approachusing System;Ā
public class GFG {Ā
Ā Ā Ā Ā // A utility function to get max of two integersĀ Ā Ā Ā static int max(int x, int y) { return (x > y) ? x : y; }Ā Ā Ā Ā // Returns the length of the longest palindromicĀ Ā Ā Ā // subsequence in seqĀ
Ā Ā Ā Ā static int lps(char[] seq, int i, int j)Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā // Base Case 1: If there is only 1 characterĀ Ā Ā Ā Ā Ā Ā Ā if (i == j) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return 1;Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Base Case 2: If there are only 2 characters andĀ Ā Ā Ā Ā Ā Ā Ā // both are sameĀ Ā Ā Ā Ā Ā Ā Ā if (seq[i] == seq[j] && i + 1 == j) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return 2;Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā // If the first and last characters matchĀ Ā Ā Ā Ā Ā Ā Ā if (seq[i] == seq[j]) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return lps(seq, i + 1, j - 1) + 2;Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā // If the first and last characters do not matchĀ Ā Ā Ā Ā Ā Ā Ā return max(lps(seq, i, j - 1), lps(seq, i + 1, j));Ā Ā Ā Ā }Ā
Ā Ā Ā Ā /* Driver program to test above function */Ā Ā Ā Ā public static void Main()Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā String seq = "GEEKSFORGEEKS";Ā Ā Ā Ā Ā Ā Ā Ā int n = seq.Length;Ā Ā Ā Ā Ā Ā Ā Ā Console.Write("The length of the LPS is "Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā + lps(seq.ToCharArray(), 0, n - 1));Ā Ā Ā Ā }}Ā
// This code is contributed by Rajput-Ji |
Javascript
// A utility function to get max of two integersĀ Ā Ā Ā Ā function max(x, y)Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā return (x > y) ? x : y; Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā Ā // Returns the length of the longest palindromic subsequence in seqĀ Ā Ā Ā Ā Ā Ā Ā function lps(seq, i, j)Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā // Base Case 1: If there is only 1 character Ā Ā Ā Ā Ā Ā Ā Ā if (i == j)Ā Ā Ā Ā Ā Ā Ā Ā { Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return 1; Ā Ā Ā Ā Ā Ā Ā Ā } Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // Base Case 2: If there are only 2 characters and both are sameĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (seq[i] == seq[j] && i + 1 == j)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā { Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return 2; Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā } Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // If the first and last characters matchĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (seq[i] == seq[j]) Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā { Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return lps(seq, i + 1, j - 1) + 2; Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā } Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // If the first and last characters do not matchĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return max(lps(seq, i, j - 1), lps(seq, i + 1, j)); Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā Ā /* Driver program to test above function */Ā Ā Ā Ā let seq = "GEEKSFORGEEKS"; Ā Ā Ā Ā let n = seq.length;Ā Ā Ā Ā console.log("The length of the LPS is ", lps(seq.split(""), 0, n - 1));Ā Ā Ā Ā Ā Ā Ā Ā Ā // This code is contributed by avanitrachhadiya2155 |
Output
The length of the LPS is 5
Time complexity: O(2n), where ānā is the length of the input sequence.
Auxiliary Space: O(n2) as we are using a 2D array to store the solutions of the subproblems.
Using the Memoization Technique of Dynamic Programming:Ā
The idea used here is to reverse the given input string and check the length of the longest common subsequence. That would be the answer for the longest palindromic subsequence.
Below is the implementation for the above approach:
C++
// A Dynamic Programming based C++ program// for LPS problem returns the length of// the longest palindromic subsequence// in seq#include <bits/stdc++.h>using namespace std;Ā
int dp[1001][1001];Ā
// Returns the length of the longest// palindromic subsequence in seqint lps(string& s1, string& s2, int n1, int n2){Ā Ā Ā Ā if (n1 == 0 || n2 == 0) {Ā Ā Ā Ā Ā Ā Ā Ā return 0;Ā Ā Ā Ā }Ā Ā Ā Ā if (dp[n1][n2] != -1) {Ā Ā Ā Ā Ā Ā Ā Ā return dp[n1][n2];Ā Ā Ā Ā }Ā Ā Ā Ā if (s1[n1 - 1] == s2[n2 - 1]) {Ā Ā Ā Ā Ā Ā Ā Ā return dp[n1][n2] = 1 + lps(s1, s2, n1 - 1, n2 - 1);Ā Ā Ā Ā }Ā Ā Ā Ā else {Ā Ā Ā Ā Ā Ā Ā Ā return dp[n1][n2] = max(lps(s1, s2, n1 - 1, n2),Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā lps(s1, s2, n1, n2 - 1));Ā Ā Ā Ā }}Ā
// Driver program to test above functionsint main(){Ā Ā Ā Ā string seq = "GEEKSFORGEEKS";Ā Ā Ā Ā int n = seq.size();Ā Ā Ā Ā dp[n][n];Ā Ā Ā Ā memset(dp, -1, sizeof(dp));Ā Ā Ā Ā string s2 = seq;Ā Ā Ā Ā reverse(s2.begin(), s2.end());Ā Ā Ā Ā cout << "The length of the LPS is "Ā Ā Ā Ā Ā Ā Ā Ā Ā << lps(s2, seq, n, n) << endl;Ā Ā Ā Ā return 0;} |
Java
// Java program of above approachimport java.io.*;import java.util.*;class GFG {Ā
Ā Ā Ā Ā // A utility function to get max of two integersĀ Ā Ā Ā static int max(int x, int y) { return (x > y) ? x : y; }Ā
Ā Ā Ā Ā // Returns the length of the longest palindromicĀ Ā Ā Ā // subsequence in seqĀ Ā Ā Ā static int lps(char seq[], int i, int j, int dp[][])Ā Ā Ā Ā {Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Base Case 1: If there is only 1 characterĀ Ā Ā Ā Ā Ā Ā Ā if (i == j) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return dp[i][j] = 1;Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Base Case 2: If there are only 2 characters andĀ Ā Ā Ā Ā Ā Ā Ā // both are sameĀ Ā Ā Ā Ā Ā Ā Ā if (seq[i] == seq[j] && i + 1 == j) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return dp[i][j] = 2;Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā // Avoid extra call for already calculatedĀ Ā Ā Ā Ā Ā Ā Ā // subproblems, Just return the saved ans from cacheĀ Ā Ā Ā Ā Ā Ā Ā if (dp[i][j] != -1) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return dp[i][j];Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā // If the first and last characters matchĀ Ā Ā Ā Ā Ā Ā Ā if (seq[i] == seq[j]) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return dp[i][j]Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā = lps(seq, i + 1, j - 1, dp) + 2;Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā // If the first and last characters do not matchĀ Ā Ā Ā Ā Ā Ā Ā return dp[i][j] = max(lps(seq, i, j - 1, dp),Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā lps(seq, i + 1, j, dp));Ā Ā Ā Ā }Ā
Ā Ā Ā Ā /* Driver program to test above function */Ā Ā Ā Ā public static void main(String[] args)Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā String seq = "GEEKSFORGEEKS";Ā Ā Ā Ā Ā Ā Ā Ā int n = seq.length();Ā Ā Ā Ā Ā Ā Ā Ā int dp[][] = new int[n][n];Ā Ā Ā Ā Ā Ā Ā Ā for (int[] arr : dp)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Arrays.fill(arr, -1);Ā Ā Ā Ā Ā Ā Ā Ā System.out.printf(Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā "The length of the LPS is %d",Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā lps(seq.toCharArray(), 0, n - 1, dp));Ā Ā Ā Ā }}Ā
// This code is contributed by gauravrajput1 |
Python3
# A Dynamic Programming based Python program for LPS problem# Returns the length of the longest palindromic subsequence# in seqĀ
dp = [[-1 for i in range(1001)]for j in range(1001)]Ā
# Returns the length of the longest palindromic subsequence# in seqĀ
Ā
def lps(s1, s2, n1, n2):Ā
Ā Ā Ā Ā if (n1 == 0 or n2 == 0):Ā Ā Ā Ā Ā Ā Ā Ā return 0Ā
Ā Ā Ā Ā if (dp[n1][n2] != -1):Ā Ā Ā Ā Ā Ā Ā Ā return dp[n1][n2]Ā
Ā Ā Ā Ā if (s1[n1 - 1] == s2[n2 - 1]):Ā Ā Ā Ā Ā Ā Ā Ā dp[n1][n2] = 1 + lps(s1, s2, n1 - 1, n2 - 1)Ā Ā Ā Ā Ā Ā Ā Ā return dp[n1][n2]Ā Ā Ā Ā else:Ā Ā Ā Ā Ā Ā Ā Ā dp[n1][n2] = max(lps(s1, s2, n1 - 1, n2), lps(s1, s2, n1, n2 - 1))Ā Ā Ā Ā Ā Ā Ā Ā return dp[n1][n2]Ā
# Driver program to test above functionsĀ
Ā
seq = "GEEKSFORGEEKS"n = len(seq)Ā
s2 = seqs2 = s2[::-1]print(f"The length of the LPS is {lps(s2, seq, n, n)}")Ā
# This code is contributed by shinjanpatra |
C#
// C# code to implement the approachusing System;using System.Numerics;using System.Collections.Generic;Ā
public class GFG {Ā
Ā Ā Ā Ā // A utility function to get max of two integersĀ Ā Ā Ā static int max(int x, int y) { return (x > y) ? x : y; }Ā
Ā Ā Ā Ā // Returns the length of the longest palindromicĀ Ā Ā Ā // subsequence in seqĀ Ā Ā Ā static int lps(char[] seq, int i, int j)Ā Ā Ā Ā {Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Base Case 1: If there is only 1 characterĀ Ā Ā Ā Ā Ā Ā Ā if (i == j) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return 1;Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Base Case 2: If there are only 2 characters andĀ Ā Ā Ā Ā Ā Ā Ā // both are sameĀ Ā Ā Ā Ā Ā Ā Ā if (seq[i] == seq[j] && i + 1 == j) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return 2;Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā // If the first and last characters matchĀ Ā Ā Ā Ā Ā Ā Ā if (seq[i] == seq[j]) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā return lps(seq, i + 1, j - 1) + 2;Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā // If the first and last characters do not matchĀ Ā Ā Ā Ā Ā Ā Ā return max(lps(seq, i, j - 1), lps(seq, i + 1, j));Ā Ā Ā Ā }Ā
Ā Ā Ā Ā // Driver CodeĀ Ā Ā Ā public static void Main(string[] args)Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā string seq = "GEEKSFORGEEKS";Ā Ā Ā Ā Ā Ā Ā Ā int n = seq.Length;Ā Ā Ā Ā Ā Ā Ā Ā Console.Write("The length of the LPS is "Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā + lps(seq.ToCharArray(), 0, n - 1));Ā Ā Ā Ā }}Ā
// This code is contributed by sanjoy_62. |
Javascript
// A Dynamic Programming based JavaScript program for LPS problem// Returns the length of the longest palindromic subsequence// in seqlet dp;Ā
// Returns the length of the longest palindromic subsequence// in seqfunction lps(s1, s2, n1, n2){Ā Ā Ā Ā if (n1 == 0 || n2 == 0) {Ā Ā Ā Ā Ā Ā Ā Ā return 0;Ā Ā Ā Ā }Ā Ā Ā Ā if (dp[n1][n2] != -1) {Ā Ā Ā Ā Ā Ā Ā Ā return dp[n1][n2];Ā Ā Ā Ā }Ā Ā Ā Ā if (s1[n1 - 1] == s2[n2 - 1]) {Ā Ā Ā Ā Ā Ā Ā Ā return dp[n1][n2] = 1 + lps(s1, s2, n1 - 1, n2 - 1);Ā Ā Ā Ā }Ā Ā Ā Ā else {Ā Ā Ā Ā Ā Ā Ā Ā return dp[n1][n2] = Math.max(lps(s1, s2, n1 - 1, n2),Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā lps(s1, s2, n1, n2 - 1));Ā Ā Ā Ā }}Ā
/* Driver program to test above functions */Ā
let seq = "GEEKSFORGEEKS";let n = seq.length;dp = new Array(1001);for(let i=0;i<1001;i++){Ā Ā Ā Ā dp[i] = new Array(1001).fill(-1);}let s2 = seq;s2 = s2.split('').reverse().join('');console.log("The length of the LPS is " + lps(s2, seq, n, n),"</br>");Ā Ā // This code is contributed by shinjanpatra |
Output
The length of the LPS is 5
Time Complexity: O(n2)
Auxiliary Space: O(n2)
Using the Tabulation technique of Dynamic programming to find LPS:Ā
In the earlier sections, we discussed recursive and dynamic programming approaches with memoization for solving the Longest Palindromic Subsequence (LPS) problem. Now, we will shift our focus to the Bottom-up dynamic programming method.
Below is the implementation for the above approach:
C++
// A Dynamic Programming based C++ program for LPS problem// Returns the length of the longest palindromic subsequence#include <algorithm>#include <cstring> // for memset#include <iostream>#include <string>Ā
using namespace std;Ā
int longestPalinSubseq(string S){Ā Ā Ā Ā string R = S;Ā Ā Ā Ā reverse(R.begin(), R.end());Ā
Ā Ā Ā Ā // dp[i][j] will store the length of the longestĀ Ā Ā Ā // palindromic subsequence for the substringĀ Ā Ā Ā // starting at index i and ending at index jĀ Ā Ā Ā int dp[S.length() + 1][R.length() + 1];Ā
Ā Ā Ā Ā // Initialize dp array with zerosĀ Ā Ā Ā memset(dp, 0, sizeof(dp));Ā
Ā Ā Ā Ā // Filling up DP table based on conditions discussedĀ Ā Ā Ā // in the above approachĀ Ā Ā Ā for (int i = 1; i <= S.length(); i++) {Ā Ā Ā Ā Ā Ā Ā Ā for (int j = 1; j <= R.length(); j++) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (S[i - 1] == R[j - 1])Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā dp[i][j] = 1 + dp[i - 1][j - 1];Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā elseĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā }Ā
Ā Ā Ā Ā // At the end, DP table will contain the LPSĀ Ā Ā Ā // So just return the length of LPSĀ Ā Ā Ā return dp[S.length()][R.length()];}Ā
// Driver codeint main(){Ā Ā Ā Ā string s = "GEEKSFORGEEKS";Ā Ā Ā Ā cout << "The length of the LPS is "Ā Ā Ā Ā Ā Ā Ā Ā Ā << longestPalinSubseq(s) << endl;Ā
Ā Ā Ā Ā return 0;}Ā
// This code is contributed by akshitaguprzj3 |
Java
// A Dynamic Programming based Java program for LPS problem// Returns the length of the longest palindromic subsequenceimport java.io.*;import java.util.*;Ā
class GFG {Ā Ā Ā Ā public static int longestPalinSubseq(String S)Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā String RĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā = new StringBuilder(S).reverse().toString();Ā
Ā Ā Ā Ā Ā Ā Ā Ā // dp[i][j] will store the length of the longestĀ Ā Ā Ā Ā Ā Ā Ā // palindromic subsequence for the substringĀ Ā Ā Ā Ā Ā Ā Ā // starting at index i and ending at index jĀ Ā Ā Ā Ā Ā Ā Ā int dp[][]Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā = new int[S.length() + 1][R.length() + 1];Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Filling up DP table based on conditions discussedĀ Ā Ā Ā Ā Ā Ā Ā // in above approachĀ Ā Ā Ā Ā Ā Ā Ā for (int i = 1; i <= S.length(); i++) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā for (int j = 1; j <= R.length(); j++) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (S.charAt(i - 1) == R.charAt(j - 1))Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā dp[i][j] = 1 + dp[i - 1][j - 1];Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā elseĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā dp[i][j] = Math.max(dp[i][j - 1],Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā dp[i - 1][j]);Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā // At the end DP table will contain the LPSĀ Ā Ā Ā Ā Ā Ā Ā // So just return the length of LPSĀ Ā Ā Ā Ā Ā Ā Ā return dp[S.length()][R.length()];Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā // Driver codeĀ Ā Ā Ā public static void main(String[] args)Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā String s = "GEEKSFORGEEKS";Ā Ā Ā Ā Ā Ā Ā Ā System.out.println("The length of the LPS is "Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā + longestPalinSubseq(s));Ā Ā Ā Ā }} |
Python3
def longestPalinSubseq(S):Ā Ā Ā Ā R = S[::-1]Ā
Ā Ā Ā Ā # dp[i][j] will store the length of the longestĀ Ā Ā Ā # palindromic subsequence for the substringĀ Ā Ā Ā # starting at index i and ending at index jĀ Ā Ā Ā dp = [[0] * (len(R) + 1) for _ in range(len(S) + 1)]Ā
Ā Ā Ā Ā # Filling up DP table based on conditions discussedĀ Ā Ā Ā # in the above approachĀ Ā Ā Ā for i in range(1, len(S) + 1):Ā Ā Ā Ā Ā Ā Ā Ā for j in range(1, len(R) + 1):Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if S[i - 1] == R[j - 1]:Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā dp[i][j] = 1 + dp[i - 1][j - 1]Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā else:Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])Ā
Ā Ā Ā Ā # At the end, DP table will contain the LPSĀ Ā Ā Ā # So just return the length of LPSĀ Ā Ā Ā return dp[len(S)][len(R)]Ā
Ā
# Driver codes = "GEEKSFORGEEKS"print("The length of the LPS is", longestPalinSubseq(s))Ā
# This code is contributed by shivamgupta310570 |
C#
using System;Ā
public class GFG {Ā
Ā Ā Ā Ā // Function to find the length of the longestĀ Ā Ā Ā // palindromic subsequenceĀ Ā Ā Ā static int LongestPalinSubseq(string S)Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā char[] charArray = S.ToCharArray();Ā Ā Ā Ā Ā Ā Ā Ā Array.Reverse(charArray);Ā Ā Ā Ā Ā Ā Ā Ā string R = new string(charArray);Ā
Ā Ā Ā Ā Ā Ā Ā Ā // dp[i][j] will store the length of the longestĀ Ā Ā Ā Ā Ā Ā Ā // palindromic subsequence for the substringĀ Ā Ā Ā Ā Ā Ā Ā // starting at index i and ending at index jĀ Ā Ā Ā Ā Ā Ā Ā int[, ] dp = new int[S.Length + 1, R.Length + 1];Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Initialize dp array with zerosĀ Ā Ā Ā Ā Ā Ā Ā for (int i = 0; i <= S.Length; i++) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā for (int j = 0; j <= R.Length; j++) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā dp[i, j] = 0;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Filling up DP table based on conditions discussedĀ Ā Ā Ā Ā Ā Ā Ā // in the above approachĀ Ā Ā Ā Ā Ā Ā Ā for (int i = 1; i <= S.Length; i++) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā for (int j = 1; j <= R.Length; j++) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (S[i - 1] == R[j - 1])Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā dp[i, j] = 1 + dp[i - 1, j - 1];Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā elseĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā dp[i, j] = Math.Max(dp[i, j - 1],Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā dp[i - 1, j]);Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā // At the end, DP table will contain the LPSĀ Ā Ā Ā Ā Ā Ā Ā // So just return the length of LPSĀ Ā Ā Ā Ā Ā Ā Ā return dp[S.Length, R.Length];Ā Ā Ā Ā }Ā
Ā Ā Ā Ā // Driver codeĀ Ā Ā Ā public static void Main(string[] args)Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā string s = "GEEKSFORGEEKS";Ā Ā Ā Ā Ā Ā Ā Ā Console.WriteLine("The length of the LPS is "Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā + LongestPalinSubseq(s));Ā Ā Ā Ā }}Ā
// This code is contributed by shivamgupta310570 |
Javascript
// A Dynamic Programming based C++ program for LPS problem// Returns the length of the longest palindromic subsequenceĀ
function longestPalinSubseq(S){Ā Ā Ā Ā let R = S.split('').reverse().join('');Ā
Ā Ā Ā Ā // dp[i][j] will store the length of the longestĀ Ā Ā Ā // palindromic subsequence for the substringĀ Ā Ā Ā // starting at index i and ending at index jĀ Ā Ā Ā Ā Ā Ā Ā Ā // Initialize dp array with zerosĀ Ā Ā Ā let dp = new Array(S.length + 1).fill(0).map(() => new Array(R.length + 1).fill(0));Ā
Ā Ā Ā Ā // Filling up DP table based on conditions discussedĀ Ā Ā Ā // in the above approachĀ Ā Ā Ā for (let i = 1; i <= S.length; i++) {Ā Ā Ā Ā Ā Ā Ā Ā for (let j = 1; j <= R.length; j++) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (S[i - 1] == R[j - 1])Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā dp[i][j] = 1 + dp[i - 1][j - 1];Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā elseĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā }Ā
Ā Ā Ā Ā // At the end, DP table will contain the LPSĀ Ā Ā Ā // So just return the length of LPSĀ Ā Ā Ā return dp[S.length][R.length];}Ā
// Driver codelet s = "GEEKSFORGEEKS";console.log("The length of the LPS is " + longestPalinSubseq(s)); |
Output
The length of the LPS is 5
Time Complexity : O(n2)
Auxiliary Space: O(n2), since we use a 2-D array.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
