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):

1. If the characters at positions i and j 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].
2. 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:

1. Initialize a 2D array, dp, of size n x n, where n is the length of the input string s. Each element dp[i][j] will represent the length of the longest palindromic subsequence in the substring s[i...j].

2. 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.

3. The array dp is then filled in diagonal order. This is because to calculate dp[i][j], we need to have already calculated dp[i+1][j-1], dp[i][j-1], and dp[i+1][j].

4. For each element dp[i][j] (where i < 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 to dp[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 excluding s[i] or s[j]. So, dp[i][j] is set to the maximum of dp[i][j-1] and dp[i+1][j].

5. 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.

Example 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.

1. Initialize the 2D array dp of size 5x5 (since the length of s is 5). This dp 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     ]

2. 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     ]

3. 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.

4. When s[i] == s[j], we set dp[i][j] to dp[i+1][j-1] + 2. When s[i] != s[j], we set dp[i][j] to the maximum of dp[i][j-1] and dp[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]

5. Finally, dp[0][n-1] which is dp[0][4] contains the length of the longest palindromic subsequence of the entire string s. In this case, it is 4.

   The string s = "bbbab" has a longest palindromic subsequence of length 4, which can be bbbb or bbab.

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

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.