# Longest palindrome subsequence with O(n) space

Given a sequence, find the length of the longest palindromic subsequence in it. Examples:

```Input : abbaab
Output : 4

Input : geeksforgeeks
Output : 5
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

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 ` `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

 `= 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. ` `?> `

```5
```

Time Complexity : O(n*n)
Auxiliary Space : O(n)