Longest Palindromic Subsequence

Problem Statement

Given a string 'S', your objective is to identify the length of the longest palindromic subsequence. In simpler terms, you're tasked with finding the longest sequence of characters in 'S' that can be read the same forwards and backwards, but not necessarily in consecutive order.

Example

Approach-1: Using Recursive Solution

1. Base case: If a single character is considered, it's always a palindrome of length 1.
2. If the first and last characters are different: In this case, the length of the LPS is the maximum of either excluding the first character or excluding the last character.
3. If there are only 2 characters and both are the same: In this scenario, the length of the LPS is 2.
4. If the first and last characters are the same: Here, we add 2 to the length of the LPS of the substring excluding the first and last characters.

Dry Run:

Code Implementation

C++:

Java:

Python:

Output :

Complexity Analysis

• Time Complexity - Since we are recurring for each subsequence of string $s$, the overall time complexity is equal to the number of possible subsequences which is nothing but $O(2^n)$.
• Space Complexity - Though we are not using any auxiliary data structure, due to multiple sub-problems the maximum height of the recursive stack can reach up to $n$, hence overall space complexity is $O(n)$.

Approach-2: Memoization Technique

1. Create a Memoization Table: Initialize a 2D memoization table dp of size n x n. Initialize all values in dp to -1 initially.
2. Modify the Recursive Function: Modify the recursive function to check the memoization table before making recursive calls. If the value for the current indices (i, j) is already computed, return the stored value from the memoization table.

Code Implementation

C++:

Java:

Python:

Output:

Complexity Analysis

• Time Complexity - The time complexity of memoization code has now been reduced to $O(n^2)$ from $O(2^n)$, due to which the problem becomes solvable as per the given constraints of the question.
• Space Complexity - As we are using an auxiliary 2-D array of dimension $n\times n$ due to which the space complexity becomes $O(n\times n) = O(n^2)$.

Approach-3: Using the Tabulation Technique of Dynamic Programming

We will define our DP state $i.e.$ dp[i][j] which denotes the length of the LPS of the string $s[i...j]$. Then we will see the state transitions -

Algorithm

Now we will use the gap strategy to fill the dp table step-by-step using the following logic. Let $s$ be the string of length $n$, we will start filling the dp table for all substring with gap 0 then with gap 1, and so on till the gap of $n-1$. Here $gap=k$ means all substring with gap $k$ $i.e$ $s[i...j]$ such that $j-i=k$.

• Declare a 2-D array $dp$ of size $n\times n$.
• Iterate for $gap = 0$ to $gap = n-1$ and do the following -
• Declare a variable say $i$ and initialize it to 0.
• Iterate for $j=gap$ to $j=n-1$ and do the following -
• Fill the dp[i][j] as per the state transitions described above.
• Increment i by 1, $i.e.$ i++
• Now dp[0][n-1] will contain the length of the LPS for string $s[0...n-1]$ $i.e.$ original string. Hence, we will return it as the answer.

Code Implementation

C++:

Java:

Python:

Output:

Complexity Analysis

• Time Complexity - In the first iteration the inner loop runs for $n$ time, in the second iteration it runs for $n-1$ time, and similarly in the $(n-1)^{th}$ iteration inner loop runs for 1 time. Hence the total number of executions of the inner loop is $n + (n-1) + (n-2)+...+1$ which is an order of $n^2$ and hence the time complexity is $O(n^2)$.
• Space Complexity - We have used a 2-D array of dimension $n\times n$ due to which the space complexity is $O(n^2)$.

Explore Scaler Topics Data Structures Tutorial and enhance your DSA skills with Reading Tracks and Challenges.