Longest Palindromic Subsequence and Substring
Apply interval DP to find the longest palindromic subsequence and the expand-around-centre trick for the longest palindromic substring.
Palindrome Definitions Revisited
A palindromic subsequence is a subsequence (elements not necessarily contiguous) that reads the same forwards and backwards. A palindromic substring requires contiguous characters. For 'bbbab' the longest palindromic subsequence is 'bbbb' (length 4), while the longest palindromic substring is 'bbb' (length 3). These two problems require different techniques despite their similar names.
Longest Palindromic Subsequence: LPS State
Define dp[i][j] as the length of the longest palindromic subsequence in s[i..j]. The recurrence is: if s[i] == s[j], then dp[i][j] = dp[i+1][j-1] + 2 (the two matching characters extend the inner palindrome). Otherwise, dp[i][j] = max(dp[i+1][j], dp[i][j-1]) (skip the left or right character). Base case: dp[i][i] = 1 for all single characters.
s = 'bbbab'
n = len(s)
dp = [[0]*n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
print('Base cases set, dp[i][i] = 1 for all i')All lessons in this course
- Interval DP Pattern and Fill Order
- Longest Palindromic Subsequence and Substring
- Palindrome Partitioning II
- Burst Balloons: Reverse Interval DP