## Problem Statement

Given a string **S**, find the common palindromic sequence ( A sequence that does not need to be contiguous and is a palindrome), which is common in itself.

You need to return the length of the longest palindromic subsequence in A.

A string is said to be palindrome if the reverse of the string is the same as the string. For example, “abba” is a palindrome, but “abbc” is not a palindrome.

**Examples:**

**Input: **S = “BEBEEED”**Output: **4**Explanation:**

The longest common palindromic subsequence is “EEEE”, which has a length of 4**Input: **S = “AABCDEBAZ”**Output:** 5

## Brute force: Recursion Approach

A simple approach to solve this problem is to generate all the subsequences of the given string and find the longest palindromic string among all the generated strings. There are a total of 2^N strings possible, where N denotes the length of the given string.

The idea is to check and compare the first and last characters of the string. There are only **two** possibilities for the same:

- If the first and the last characters are the same, it can be ensured that both the characters can be considered in the final palindrome and hence, add
**2**to the result, since we have found a sequence of length**2**and recurse the remaining substring**S[i + 1, j – 1]**. - In case, the first and the last characters aren’t the same, the following operation must be performed:
- Recurse
**S[i + 1, j]** - Recurse
**S[ i, j – 1]**

- Recurse
- Find the maximum length obtained amongst them.

The recursion tree can be shown as follows: **LPS(1, N) **denotes the length of the longest palindromic subsequence of the given string **S[1..N].**

### C++ Implementation

int LPS(string S, int left, int right){ if (left > right) { return 0; } if(left == right){ return 1; } if (S[left] == S[right]) { return 2 + LPS(str,left+1,right-1); } return max(LPS(S, left, right - 1), LPS(S, left + 1, right)); }

Practice on our C++ Compiler

### Java Implementation

static int LPS(String S, int left, int right){ if (left > right) { return 0; } if(left == right){ return 1; } if (S.charAt(left) == S.charAt(right) ) { return 2 + LPS(str,left+1,right-1); } return Math.max(LPS(S, left, right - 1), LPS(S, left + 1, right)); }

Practice on our Java Compiler

### Python Implementation

def LPS(S, left, right){ if left > right: return 0 If left == right: return 1 if S[left] == S[right]: return 2 + LPS(str,left+1,right-1); return max(LPS(S, left, right - 1), LPS(S, left + 1, right))

Practice on our Python Compiler

**Time Complexity:** O(2^N) where N is the size of the string **S**.**Space Complexity:** O(1), as no extra space is used.

## Efficient Approach (Using Dynamic Programming)

The efficient approach uses a dynamic programming approach for the problem.

It can be clearly observed that some of the subsequences are repeating i.e it contains **overlapping subproblems**. Let us take the example of the string **ABCDE**.

The subproblems **BCD **is repeating twice, hence instead of calculating the value twice, we can instead store it in a table. Let’s illustrate the algorithm with the string – **“axbdba”**.

Consider a **dp **array of size **N * N**.

**Algorithm: **

Fill the table with a start case, **dp[i, i] == 1**, since all single char in a string is a palindrome, which length is 1.

When s[i] == s[j]

When s[i] == s[j]

Continue the process until the whole dp array is filled.

Return **dp[0][N – 1] **is the **longest palindromic subsequence(LPS)**

### C++ Code for DP Approach

public int LPS(string S) { int dp[S.length()][S.length()]; for (int i = S.length() - 1; i >= 0; i--) { dp[i][i] = 1; for (int j = i+1; j < S.length(); j++) { if (S[i] == S[j]) { dp[i][j] = dp[i+1][j-1] + 2; } else { dp[i][j] = max(dp[i+1][j], dp[i][j-1]); } } } return dp[0][S.length()-1]; }

### Java Code for DP Approach

public int LPS(String S) { int[][] dp = new int[S.length()][S.length()]; for (int i = S.length() - 1; i >= 0; i--) { dp[i][i] = 1; for (int j = i+1; j < S.length(); j++) { if (S.charAt(i) == S.charAt(j)) { dp[i][j] = dp[i+1][j-1] + 2; } else { dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]); } } } return dp[0][S.length()-1]; }

### Python Code for DP Approach

def LPS(S): dp = [[0 for x in range(len(S))] for x in range(len(S))] for i in range(len(S) - 1, -1, -1): dp[i][i] = 1; for j in range(i + 1, len(S)): if S[i] == S[j]: dp[i][j] = dp[i+1][j-1] + 2; else: dp[i][j] = max(dp[i+1][j], dp[i][j-1]); return dp[0][S.length()-1];

**Time Complexity:** O(N^2) where N is the size of the string **S**.**Space Complexity:** O(N^2), as extra **dp** array is used.

## Practice Question

Longest Palindromic Subsequence

## Frequently Asked Questions

**How to find the longest palindromic subsequence?**The

**LPS**can be calculated efficiently using the dynamic programming approach, which can be solved in O(N^2), where N is the size of the given string.

**How to find the palindromic subsequence from the table?**To find the subsequence, which gives us the longest

**LPS**, backtrack from

**dp[0][N – 1]**and trace the path back to

**dp[0][0].**