516. Longest Palindromic Subsequence
Problem Description
The problem asks us to find the length of the longest palindromic subsequence within a given string s
. A subsequence is defined as a sequence that can be obtained from another sequence by deleting zero or more characters without changing the order of the remaining characters. Unlike substrings, subsequences are not required to occupy consecutive positions within the original string. A palindromic subsequence is one that reads the same backward as forward.
Intuition
The intuition behind the solution is to use dynamic programming to build up the solution by finding the lengths of the longest palindromic subsequences within all substrings of s
, and then use these results to find the length of the longest palindromic subsequence of the whole string.
The key idea is to create a 2D array dp
where dp[i][j]
represents the length of the longest palindromic subsequence of the substring s[i:j+1]
.
To fill this table, we start with the simplest case: a substring of length 1, which is always a palindrome of length 1. Then, we gradually consider longer substrings by increasing the length and using the previously computed values.
When we look at a substring [i, j]
(where i
is the starting index and j
is the ending index):
- If the characters at positions
i
andj
are the same, then the length of the longest palindromic subsequence of[i, j]
is two plus the length of the longest palindromic subsequence of[i + 1, j - 1]
. - If the characters are different, the longest palindromic subsequence of
[i, j]
is the longer of the longest palindromic subsequences of[i + 1, j]
and[i, j - 1]
.
We continue this process, eventually filling in the dp
table for all possible substrings, and the top-right cell of the table (dp[0][n-1]
, where n
is the length of the original string) will contain the length of the longest palindromic subsequence of s
.
Learn more about Dynamic Programming patterns.
Solution Approach
The implementation uses dynamic programming to solve the problem as follows:
-
Initialize a 2D array,
dp
, of sizen x n
, wheren
is the length of the input strings
. Each elementdp[i][j]
will represent the length of the longest palindromic subsequence in the substrings[i...j]
. -
Populate the diagonal of
dp
with 1s because a single character is always a palindrome with a length of 1. We're certain that the longest palindromic subsequence in a string of length 1 is the string itself. -
The array
dp
is then filled in diagonal order. This is because to calculatedp[i][j]
, we need to have already calculateddp[i+1][j-1]
,dp[i][j-1]
, anddp[i+1][j]
. -
For each element
dp[i][j]
(wherei < j
), two cases are possible:- If
s[i] == s[j]
, the characters at both ends of the current substring match, and they could potentially be part of the longest palindromic subsequence. Therefore,dp[i][j]
is set todp[i+1][j-1] + 2
, adding 2 to account for the two matching characters. - If
s[i] != s[j]
, the characters at both ends of the substring do not match. We must find whether the longer subsequence occurs by excludings[i]
ors[j]
. So,dp[i][j]
is set to the maximum ofdp[i][j-1]
anddp[i+1][j]
.
- If
-
After filling up the array,
dp[0][n-1]
will contain the length of the longest palindromic subsequence in the entire string, since it represents the substring from the first character to the last.
The solution approach efficiently computes the longest palindromic subsequence by systematically solving smaller subproblems and combining them to form the solution to the original problem.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use the string s = "bbbab"
to illustrate the solution approach. The goal is to find the length of the longest palindromic subsequence. We will use the implementation steps mentioned to find this length.
-
Initialize the 2D array
dp
of size 5x5 (since the length ofs
is 5). Thisdp
will store lengths of the longest palindromic subsequences for different substrings.Initially,
dp
looks like this (zero-initialized for non-diagonal elements):1dp = [ 2 [0, 0, 0, 0, 0], 3 [0, 0, 0, 0, 0], 4 [0, 0, 0, 0, 0], 5 [0, 0, 0, 0, 0], 6 [0, 0, 0, 0, 0] 7 ]
-
Populate the diagonal with 1s, because any single character is itself a palindrome of length 1.
After this step,
dp
looks like this:1dp = [ 2 [1, 0, 0, 0, 0], 3 [0, 1, 0, 0, 0], 4 [0, 0, 1, 0, 0], 5 [0, 0, 0, 1, 0], 6 [0, 0, 0, 0, 1] 7 ]
-
Now, we start filling in the
dp
array in diagonal order, just above the main diagonal (i.e., substrings of length 2), then the next diagonal (substrings of length 3), and so on. -
When
s[i] == s[j]
, we setdp[i][j]
todp[i+1][j-1] + 2
. Whens[i] != s[j]
, we setdp[i][j]
to the maximum ofdp[i][j-1]
anddp[i+1][j]
.Filling
dp
for the substring of length 2:1dp[0][1] (s[0]: 'b', s[1]: 'b') => dp[1][0] (which is 0, a non-existing substring) + 2 = 2 2 3dp array becomes: 4[1, 2, 0, 0, 0] 5[0, 1, 0, 0, 0] 6[0, 0, 1, 0, 0] 7[0, 0, 0, 1, 0] 8[0, 0, 0, 0, 1]
Similarly, filling
dp
for all substrings of length 2 to length n-1 (n = 5):1dp array after filling in: 2[1, 2, 3, 3, 4] 3[0, 1, 2, 2, 3] 4[0, 0, 1, 1, 3] 5[0, 0, 0, 1, 2] 6[0, 0, 0, 0, 1]
-
Finally,
dp[0][n-1]
which isdp[0][4]
contains the length of the longest palindromic subsequence of the entire strings
. In this case, it is4
.The string
s = "bbbab"
has a longest palindromic subsequence of length 4, which can bebbbb
orbbab
.
The example provided demonstrates the use of dynamic programming to calculate the length of the longest palindromic subsequence step by step by building solutions to smaller subproblems.
Solution Implementation
1class Solution:
2 def longest_palindrome_subseq(self, s: str) -> int:
3 # The length of the input string
4 length = len(s)
5
6 # Initialize a 2D array with zeros, where dp[i][j] will hold the length of the longest
7 # palindromic subsequence between indices i and j in string s
8 dp = [[0] * length for _ in range(length)]
9
10 # A single character is always a palindrome of length 1,
11 # so we populate the diagonals with 1
12 for i in range(length):
13 dp[i][i] = 1
14
15 # Loop over pairs of characters from end to start of the string
16 for j in range(1, length):
17 for i in range(j - 1, -1, -1):
18 # If characters at index i and j are the same, they can form a palindrome:
19 # - Add 2 to the length of the longest palindromic subsequence we found
20 # between i + 1 and j - 1
21 if s[i] == s[j]:
22 dp[i][j] = dp[i + 1][j - 1] + 2
23 else:
24 # Otherwise, take the maximum of the lengths found by:
25 # - Excluding the j-th character (considering subsequence from i to j - 1)
26 # - Excluding the i-th character (considering subsequence from i + 1 to j)
27 dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
28
29 # The entire string's longest palindromic subsequence length is at dp[0][length-1]
30 return dp[0][length - 1]
31
1class Solution {
2 public int longestPalindromeSubseq(String s) {
3 // Length of the input string
4 int n = s.length();
5
6 // Initialize a 2D array 'dp' to store the length of the longest
7 // palindromic subsequence for substring (i, j)
8 int[][] dp = new int[n][n];
9
10 // Base case: single letters are palindromes of length 1
11 for (int i = 0; i < n; ++i) {
12 dp[i][i] = 1;
13 }
14
15 // Build the table 'dp' bottom-up such that:
16 // We start by considering all substrings of length 2, and work our way up to n.
17 for (int j = 1; j < n; ++j) {
18 for (int i = j - 1; i >= 0; --i) {
19 // If the characters at positions i and j are the same
20 // they can form a palindrome with the palindrome from substring (i+1, j-1)
21 if (s.charAt(i) == s.charAt(j)) {
22 dp[i][j] = dp[i + 1][j - 1] + 2;
23 } else {
24 // If the characters at i and j do not match, then the longest palindrome
25 // within (i, j) is the maximum of (i+1, j) or (i, j-1) since we can
26 // exclude one of the characters and seek the longest within the remaining substring
27 dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
28 }
29 }
30 }
31
32 // The top-right corner of 'dp' will hold the result for the entire string (0, n-1)
33 return dp[0][n - 1];
34 }
35}
36
1class Solution {
2public:
3 // Function to find the length of the longest palindromic subsequence.
4 int longestPalindromeSubseq(string s) {
5 // Store the length of the string.
6 int length = s.size();
7
8 // Create a 2D DP array with 'length' rows and 'length' columns.
9 vector<vector<int>> dp(length, vector<int>(length, 0));
10
11 // Each single character is a palindrome of length 1.
12 for (int i = 0; i < length; ++i) {
13 dp[i][i] = 1;
14 }
15
16 // Build the DP table in a bottom-up manner.
17 for (int end = 1; end < length; ++end) {
18 for (int start = end - 1; start >= 0; --start) {
19 // If the characters at the current start and end positions are equal,
20 // we can extend the length of the palindrome subsequence by 2.
21 if (s[start] == s[end]) {
22 dp[start][end] = dp[start + 1][end - 1] + 2;
23 } else {
24 // Otherwise, we take the maximum of the two possible subsequence lengths:
25 // excluding the start character or the end character
26 dp[start][end] = max(dp[start + 1][end], dp[start][end - 1]);
27 }
28 }
29 }
30
31 // The answer is in dp[0][length - 1], which represents the longest palindromic
32 // subsequence of the entire string.
33 return dp[0][length - 1];
34 }
35};
36
1// Function to find the length of the longest palindromic subsequence
2function longestPalindromeSubseq(s: string): number {
3 // Store the length of the string
4 const length: number = s.length;
5
6 // Create a 2D DP array with 'length' rows and 'length' columns,
7 // initialized with zeros
8 const dp: number[][] = new Array(length).fill(0).map(() => new Array(length).fill(0));
9
10 // Each single character is a palindrome of length 1.
11 for (let i = 0; i < length; i++) {
12 dp[i][i] = 1;
13 }
14
15 // Build the DP table in a bottom-up manner.
16 for (let end = 1; end < length; end++) {
17 for (let start = end - 1; start >= 0; start--) {
18 // If the characters at the current start and end positions are equal,
19 // we can extend the length of the palindrome subsequence by 2.
20 if (s[start] === s[end]) {
21 dp[start][end] = dp[start + 1][end - 1] + 2;
22 } else {
23 // Otherwise, we take the maximum of the two possible subsequence lengths:
24 // excluding the start character or the end character
25 dp[start][end] = Math.max(dp[start + 1][end], dp[start][end - 1]);
26 }
27 }
28 }
29
30 // The answer is in dp[0][length - 1], which represents the longest palindromic
31 // subsequence of the entire string
32 return dp[0][length - 1];
33}
34
Time and Space Complexity
Time Complexity
The time complexity of the code is O(n^2)
, where n
is the length of the string s
. This complexity arises because the algorithm uses two nested loops: the outer loop runs from 1 to n - 1
and the inner loop runs in reverse from j - 1
to 0
. Each time the inner loop executes, the algorithm performs a constant amount of work, resulting in a total time complexity of O(n^2)
.
Space Complexity
The space complexity of the code is also O(n^2)
. This is due to the dp
table which is a 2-dimensional list of size n * n
. Each cell of the table is filled out exactly once, resulting in a total space usage directly proportional to the square of the length of the input string.
Learn more about how to find time and space complexity quickly using problem constraints.
What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.