516. Longest Palindromic Subsequence

https://leetcode.com/problems/longest-palindromic-subsequence/

Longest Palindromic Subsequence - LeetCode

 

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        # create a 2D array of size n x n to store the lengths of longest palindromic subsequence
        dp = [[0]*n for _ in range(n)]
        
        # each character is a palindrome of length 1
        for i in range(n):
            dp[i][i] = 1
            
        # loop through the string s in reverse order
        for i in range(n-1, -1, -1):
            # loop through the string s in forward order from i+1
            for j in range(i+1, n):
                if s[i] == s[j]:
                    # if characters at i and j match, add 2 to the length of longest palindromic subsequence
                    dp[i][j] = dp[i+1][j-1] + 2
                else:
                    # if characters at i and j don't match, take the maximum of two possibilities:
                    # 1. exclude character at i and find longest palindromic subsequence in the remaining substring s[i+1:j+1]
                    # 2. exclude character at j and find longest palindromic subsequence in the remaining substring s[i:j]
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])
                    
        # length of longest palindromic subsequence is stored in dp[0][n-1]
        return dp[0][n-1]