# Leetcode 516. Longest Palindromic Subsequence

[link](https://leetcode.com/problems/longest-palindromic-subsequence/)

---

Given a string s, find the longest palindromic subsequence's length in s.

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.

#### Example 1:

Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".

#### Example 2:

Input: s = "cbbd"
Output: 2
Explanation: One possible longest palindromic subsequence is "bb".

#### Constraints:

- 1 <= s.length <= 1000
- s consists only of lowercase English letters.

---

Inside the function, a dictionary dp is initialized to store previously computed results. This dictionary is used to avoid redundant calculations and improve the efficiency of the algorithm.

The code defines a helper function called dfs (depth-first search). This function takes two arguments, l (left index) and r (right index), representing the current substring being considered. It recursively explores and calculates the length of the longest palindromic subsequence for the substring defined by l and r.

In the dfs function:

If l is less than 0 or r is equal to the length of the string s, it means that we have reached the boundaries of the string. In this case, we return 0, indicating that there are no more characters to consider.

If the current substring s[l:r+1] is already in the dp dictionary (indicating that it has been calculated before), we return the precomputed result.

If the characters at positions l and r in the string are the same, we have two options:

If l is equal to r, it means we have a single character palindrome, so we add 1 to the length.
If l is not equal to r, it means we can include both characters in the palindrome, so we add 2 to the length and recursively call dfs for the substring between l + 1 and r - 1.
If the characters at positions l and r are different, we have two choices: either exclude the character at position l or exclude the character at position r. We take the maximum of these two choices.

The main loop of the longestPalindromeSubseq function iterates over each character in the input string s using the variable i.

Inside the loop, it calls the dfs function twice:

First, it calls dfs(i, i), which represents a single-character substring.

Second, it calls dfs(i, i + 1), which represents a two-character substring.

Finally, the function returns the maximum value from the dp dictionary, which represents the length of the longest palindromic subsequence found.

#### Solution 1

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        dp = {}
        def dfs(l, r):
            if l < 0 or r == len(s):
                return 0

            if (l, r) in dp:
                return dp[(l, r)]

            if s[l] == s[r]:
                length = 1 if l == r else 2
                dp[(l, r)] = length + dfs(l - 1, r + 1)
                
            else:
                dp[(l, r)] = max(dfs(l - 1, r), dfs(l, r + 1))

            return dp[(l, r)]

        for i in range(len(s)):
            dfs(i, i)
            dfs(i, i + 1)
        
        return max(dp.values())
        

O(T): O(n^2)
O(S): O(n^2)

---

Inside the function, a 2D list dp is initialized. dp has dimensions (len(s) + 1) x (len(s) + 1). The entry dp[i][j] represents the length of the longest palindromic subsequence for the substring s[i:j].

Another variable res is initialized to 0. This variable will store the maximum length of the palindromic subsequence found.

The code uses nested loops to iterate through all possible substrings of s:

The outer loop iterates over the starting index i from 0 to len(s) - 1.
The inner loop iterates over the ending index j from len(s) - 1 down to i.
Inside the loop, the code checks whether the characters at positions i and j in the string s are the same:

If they are the same, it means we can potentially extend the palindromic subsequence. Depending on whether i is equal to j, we either add 1 to the length (for a single character) or add 2 to the length (for two identical characters). Additionally, if i - 1 is greater than or equal to 0 (ensuring we don't go out of bounds), we add the value of dp[i-1][j+1] to account for the extended palindrome.
If the characters at positions i and j are not the same, we consider two possibilities:

Exclude the character at position i by setting dp[i][j] to dp[i][j + 1].
Exclude the character at position j by setting dp[i][j] to dp[i - 1][j].
We take the maximum of these two possibilities.
In each iteration of the loop, we update the res variable with the maximum length found so far.

After completing the loops, the function returns the maximum value stored in the res variable, which represents the length of the longest palindromic subsequence found in the entire string s.

#### Solution 2

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        dp = [[0] * (len(s) + 1) for _ in range(len(s) + 1)]
        res = 0

        for i in range(len(s)):
            for j in range(len(s) - 1, i - 1, -1):
                if s[i] == s[j]:
                    dp[i][j] = 1 if i == j else 2
                    if i - 1 >= 0:
                        dp[i][j] += dp[i - 1][j + 1]
                
                else:
                    dp[i][j] = dp[i][j + 1]
                    if i - 1 >= 0:
                        dp[i][j] = max(dp[i][j], dp[i - 1][j])
                res = max(res, dp[i][j])

        return res
        

O(T): O(n^2)
O(S): O(n^2)