Given a sequence, find the length of the longest palindromic subsequence in it. Examples:
Input : abbaab Output : 4 Input : neveropen Output : 5
We have discussed a Dynamic Programming solution for Longest Palindromic Subsequence which is based on below recursive formula.
// Every single character is a palindrome of length 1 L(i, i) = 1 for all indexes i in given sequence // 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)} // If there are only 2 characters and both are same Else if (j == i + 1) L(i, j) = 2 // If there are more than two characters, and first // and last characters are same Else L(i, j) = L(i + 1, j – 1) + 2
The solution discussed above takes O(n2) extra space. In this post a space optimized solution is discussed that requires O(n) extra space. The idea is to create a one dimensional array a[] of same size as given string. We make sure that a[i] stores length of longest palindromic subsequence of prefix ending with i (or substring s[0..i]).
C++
// A Space optimized Dynamic Programming based C++ // program for LPS problem #include <bits/stdc++.h> using namespace std; // Returns the length of the longest palindromic // subsequence in str int lps(string &s) { int n = s.length(); // a[i] is going to store length of longest // palindromic subsequence of substring s[0..i] int a[n]; // Pick starting point for ( int i = n - 1; i >= 0; i--) { int back_up = 0; // Pick ending points and see if s[i] // increases length of longest common // subsequence ending with s[j]. for ( int j = i; j < n; j++) { // similar to 2D array L[i][j] == 1 // i.e., handling substrings of length // one. if (j == i) a[j] = 1; // Similar to 2D array L[i][j] = L[i+1][j-1]+2 // i.e., handling case when corner characters // are same. else if (s[i] == s[j]) { // value a[j] is depend upon previous // unupdated value of a[j-1] but in // previous loop value of a[j-1] is // changed. To store the unupdated // value of a[j-1] back_up variable // is used. int temp = a[j]; a[j] = back_up + 2; back_up = temp; } // similar to 2D array L[i][j] = max(L[i][j-1], // a[i+1][j]) else { back_up = a[j]; a[j] = max(a[j - 1], a[j]); } } } return a[n - 1]; } /* Driver program to test above functions */ int main() { string str = "GEEKSFORGEEKS" ; cout << lps(str); return 0; } |
Java
// A Space optimized Dynamic Programming // based Java program for LPS problem class GFG { // Returns the length of the longest // palindromic subsequence in str static int lps(String s) { int n = s.length(); // a[i] is going to store length // of longest palindromic subsequence // of substring s[0..i] int a[] = new int [n]; // Pick starting point for ( int i = n - 1 ; i >= 0 ; i--) { int back_up = 0 ; // Pick ending points and see if s[i] // increases length of longest common // subsequence ending with s[j]. for ( int j = i; j < n; j++) { // similar to 2D array L[i][j] == 1 // i.e., handling substrings of length // one. if (j == i) a[j] = 1 ; // Similar to 2D array L[i][j] = L[i+1][j-1]+2 // i.e., handling case when corner characters // are same. else if (s.charAt(i) == s.charAt(j)) { int temp = a[j]; a[j] = back_up + 2 ; back_up = temp; } // similar to 2D array L[i][j] = max(L[i][j-1], // a[i+1][j]) else { back_up = a[j]; a[j] = Math.max(a[j - 1 ], a[j]); } } } return a[n - 1 ]; } /* Driver program to test above functions */ public static void main(String[] args) { String str = "GEEKSFORGEEKS" ; System.out.println(lps(str)); } } //This article is contributed by prerna saini. |
Python3
# A Space optimized Dynamic Programming # based Python3 program for LPS problem # Returns the length of the longest # palindromic subsequence in str def lps(s): n = len (s) # a[i] is going to store length # of longest palindromic subsequence # of substring s[0..i] a = [ 0 ] * n # Pick starting point for i in range (n - 1 , - 1 , - 1 ): back_up = 0 # Pick ending points and see if s[i] # increases length of longest common # subsequence ending with s[j]. for j in range (i, n): # similar to 2D array L[i][j] == 1 # i.e., handling substrings of length # one. if j = = i: a[j] = 1 # Similar to 2D array L[i][j] = L[i+1][j-1]+2 # i.e., handling case when corner characters # are same. elif s[i] = = s[j]: temp = a[j] a[j] = back_up + 2 back_up = temp # similar to 2D array L[i][j] = max(L[i][j-1], # a[i+1][j]) else : back_up = a[j] a[j] = max (a[j - 1 ], a[j]) return a[n - 1 ] # Driver Code string = "GEEKSFORGEEKS" print (lps(string)) # This code is contributed by Ansu Kumari. |
C#
// A Space optimized Dynamic Programming // based C# program for LPS problem using System; class GFG { // Returns the length of the longest // palindromic subsequence in str static int lps( string s) { int n = s.Length; // a[i] is going to store length // of longest palindromic subsequence // of substring s[0..i] int []a = new int [n]; // Pick starting point for ( int i = n - 1; i >= 0; i--) { int back_up = 0; // Pick ending points and see if s[i] // increases length of longest common // subsequence ending with s[j]. for ( int j = i; j < n; j++) { // similar to 2D array L[i][j] == 1 // i.e., handling substrings of length // one. if (j == i) a[j] = 1; // Similar to 2D array L[i][j] = L[i+1][j-1]+2 // i.e., handling case when corner characters // are same. else if (s[i] == s[j]) { int temp = a[j]; a[j] = back_up + 2; back_up = temp; } // similar to 2D array L[i][j] = max(L[i][j-1], // a[i+1][j]) else { back_up = a[j]; a[j] = Math.Max(a[j - 1], a[j]); } } } return a[n - 1]; } // Driver program public static void Main() { string str = "GEEKSFORGEEKS" ; Console.WriteLine(lps(str)); } } // This code is contributed by vt_m. |
PHP
<?php // A Space optimized Dynamic // Programming based PHP // program for LPS problem // Returns the length of // the longest palindromic . // subsequence in str function lps( $s ) { $n = strlen ( $s ); // Pick starting point for ( $i = $n - 1; $i >= 0; $i --) { $back_up = 0; // Pick ending points and // see if s[i] increases // length of longest common // subsequence ending with s[j]. for ( $j = $i ; $j < $n ; $j ++) { // similar to 2D array // L[i][j] == 1 i.e., // handling substrings // of length one. if ( $j == $i ) $a [ $j ] = 1; // Similar to 2D array // L[i][j] = L[i+1][j-1]+2 // i.e., handling case when // corner characters are same. else if ( $s [ $i ] == $s [ $j ]) { // value a[j] is depend // upon previous unupdated // value of a[j-1] but in // previous loop value of // a[j-1] is changed. To // store the unupdated value // of a[j-1] back_up variable // is used. $temp = $a [ $j ]; $a [ $j ] = $back_up + 2; $back_up = $temp ; } // similar to 2D array // L[i][j] = max(L[i][j-1], // a[i+1][j]) else { $back_up = $a [ $j ]; $a [ $j ] = max( $a [ $j - 1], $a [ $j ]); } } } return $a [ $n - 1]; } // Driver Code $str = "GEEKSFORGEEKS" ; echo lps( $str ); // This code is contributed // by shiv_bhakt. ?> |
Javascript
<script> // A Space optimized Dynamic Programming // based Python3 program for LPS problem // Returns the length of the longest // palindromic subsequence in str function lps(s){ let n = s.length // a[i] is going to store length // of longest palindromic subsequence // of substring s[0..i] let a = new Array(n).fill(0); // Pick starting point for (let i = n - 1; i >= 0; i--){ let back_up = 0 // Pick ending points and see if s[i] // increases length of longest common // subsequence ending with s[j]. for (let j = i; j < n; j++){ // similar to 2D array L[i][j] == 1 // i.e., handling substrings of length // one. if (j == i) a[j] = 1 // Similar to 2D array L[i][j] = L[i+1][j-1]+2 // i.e., handling case when corner characters // are same. else if (s[i] == s[j]){ let temp = a[j] a[j] = back_up + 2 back_up = temp } // similar to 2D array L[i][j] = max(L[i][j-1], // a[i+1][j]) else { back_up = a[j] a[j] = Math.max(a[j - 1], a[j]) } } } return a[n - 1] } // Driver Code let string = "GEEKSFORGEEKS" document.write(lps(string), "</br>" ) // This code is contributed by shinjanpatra </script> |
5
Time Complexity : O(n*n) Auxiliary Space : O(n)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!