Leetcode 516. Longest Palindromic Subsequence

Problem Description

In this problem, we're given a string s and we're required to find the longest palindromic subsequence's length in the string.

A palindrome is a word, number, phrase, or another sequence of characters that reads the same backward as forward (ignoring spaces, punctuation, and capitalization). For example, "madam", "20102", "racecar", "Able was I ere I saw Elba", etc.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

The maximum length of s can be up to 1000.

Solution Approach

The problem can be solved using dynamic programming.

What we do is to recursively check each substring of the input string s.

If the two end characters of the current substring are the same, we will add 2 into the count and recursively call the function for the rest of the substring without the two end characters.

If the two end characters are not the same, we decrement the substring from two ends one by one and take the maximum of their result.

Python Solution

1
2python
3class Solution:
4    def longestPalindromeSubseq(self, s: str) -> int:
5        n = len(s)
6        dp = [[0]*n for _ in range(n)]
7        
8        for i in range(n-1, -1, -1):
9            dp[i][i] = 1
10            for j in range(i+1, n):
11                if s[i] == s[j]:
12                    dp[i][j] = 2 + dp[i+1][j-1]
13                else:
14                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])
15        return dp[0][n-1]

Java Solution

1
2java
3class Solution {
4    public int longestPalindromeSubseq(String s) {
5        int[][] dp = new int[s.length()][s.length()];
6        for (int i = s.length() - 1; i >= 0; i--) {
7            dp[i][i] = 1;
8            for (int j = i+1; j < s.length(); j++) {
9                if (s.charAt(i) == s.charAt(j)) {
10                    dp[i][j] = dp[i+1][j-1] + 2;
11                } else {
12                    dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
13                }
14            }
15        }
16        return dp[0][s.length()-1];
17    }
18}

JavaScript Solution

1
2javascript
3var longestPalindromeSubseq = function(s) {
4    let dp = Array(s.length).fill(0).map(()=>Array(s.length).fill(0));
5    for(let i=s.length-1; i>=0; i--){
6        dp[i][i] = 1;
7        for(let j=i+1; j<s.length; j++){
8            if(s[i] === s[j]){
9                dp[i][j] = 2 + dp[i+1][j-1];
10            }else{
11                dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
12            }
13        }
14    }
15    return dp[0][s.length-1];
16};

C++ Solution

1
2cpp
3class Solution {
4public:
5    int longestPalindromeSubseq(string s) {
6        int n = s.size();
7        vector<vector<int>> dp(n, vector<int>(n, 0));
8        for (int i = n - 1; i >= 0; --i) {
9            dp[i][i] = 1;
10            for (int j = i + 1; j < n; ++j) {
11                if (s[i] == s[j]) {
12                    dp[i][j] = 2 + dp[i + 1][j - 1];
13                } else {
14                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
15                }
16            }
17        }
18        return dp[0][n - 1];
19    }
20};

C# Solution

1
2csharp
3public class Solution {
4    public int LongestPalindromeSubseq(string s) {
5        int[,] dp = new int[s.Length, s.Length];
6        for (int i = s.Length - 1; i >= 0; i--) {
7            dp[i, i] = 1;
8            for (int j = i + 1; j < s.Length; j++) {
9                if (s[i] == s[j]) {
10                    dp[i, j] = dp[i+1, j-1] + 2;
11                } else {
12                    dp[i, j] = Math.Max(dp[i+1, j], dp[i, j-1]);
13                }
14            }
15        }
16        return dp[0, s.Length - 1];
17    }
18}

In all these solutions, dp[i][j] stores the longest palindromic subsequence's length in s from index i to index j. Thus, at the end, we return dp[0][n-1] which represents the longest palindromic subsequence's length in the whole string s from index 0 to n-1.In these solutions, we initially create a two-dimensional array dp with a size of n x n, where n is the length of the input string s. The array is initialized with 0's.

We then start the bottom-up dynamic programming process by filling up the array. The outer loop of our program goes from the end of the string to the beginning (n-1 to 0), and the inner loop goes from the current index of the outer loop (i+1) to the end of the string (n`).

In each iteration, if the characters at the start index and at the end index are the same, we increment the length of the longest palindromic subsequence by 2 (because we have found a new palindrome that starts and ends with these two characters). We then look at the next inner substring, which is represented by dp[i+1][j-1].

If on the other hand, the characters at the start and end indices of the substring are not the same, we take the maximum length of the longest palindromic subsequence achieved so far by either incrementing the start index or decrementing the end index. This is represented by dp[i+1][j] and dp[i][j-1] respectively.

The base case for our dynamic programming process is that a single character is always a palindrome of length 1. Therefore, we set dp[i][i] = 1.

The solution to the problem (i.e., the length of the longest palindromic subsequence of the whole string) is stored in dp[0][n-1].

The time complexity of the solution is O(n^2) because we use two nested loops each running n times, where n is the length of the input string.

The space complexity is also O(n^2) because we use a two-dimensional array of size n x n to store intermediate results.

One important thing to note is that this problem asks for the length of the longest palindromic subsequence, not the longest palindromic substring. A substring is a contiguous sequence of characters within a string, while a subsequence is not necessarily contiguous, but maintains the relative order of characters. For example, in the string "character", "caat" is a subsequence but not a substring. This is why our solution considers non-contiguous characters.