DP Longest Palindromic Subsequence

Table of Contents

• 516. Longest Palindromic Subsequence (Medium)
• 730. Count Different Palindromic Subsequences (Hard)
• 1312. Minimum Insertion Steps to Make a String Palindrome (Hard)
• 1771. Maximize Palindrome Length From Subsequences (Hard)
• 1682. Longest Palindromic Subsequence II (Medium) 👑
• 1216. Valid Palindrome III (Hard) 👑
• 1246. Palindrome Removal (Hard) 👑

516. Longest Palindromic Subsequence

• LeetCode | LeetCode CH (Medium)

• Tags: string, dynamic programming

• Return the length of the longest palindromic subsequence in s.
• Bottom-up DP table

dp	b	b	b	a	b
b	1	2	3	3	4
b	0	1	2	2	3 dp[i][j]
b	0	0	1	1 dp[i+1][j-1]	2
a	0	0	0	1	1
b	0	0	0	0	1

516. Longest Palindromic Subsequence - Python Solution

def longestPalindromeSubseq(s: str) -> int:
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 1

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

    return dp[0][-1]


print(longestPalindromeSubseq("bbbab"))  # 4

730. Count Different Palindromic Subsequences

• LeetCode | LeetCode CH (Hard)

• Tags: string, dynamic programming

1312. Minimum Insertion Steps to Make a String Palindrome

• LeetCode | LeetCode CH (Hard)

• Tags: string, dynamic programming

1771. Maximize Palindrome Length From Subsequences

• LeetCode | LeetCode CH (Hard)

• Tags: string, dynamic programming

1682. Longest Palindromic Subsequence II

• LeetCode | LeetCode CH (Medium)

• Tags: string, dynamic programming

1216. Valid Palindrome III

• LeetCode | LeetCode CH (Hard)

• Tags: string, dynamic programming

1246. Palindrome Removal

• LeetCode | LeetCode CH (Hard)

• Tags: array, dynamic programming

Comments