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.
Longest Palindromic Subsequence and Substring is a free DSA Interview Prep lesson on CoddyKit — lesson 2 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
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')LPS Fill Order and Implementation
We fill the LPS table in increasing interval length, the same pattern as general interval DP. For each interval [i, j] of length 2 or more, we check whether the two boundary characters match and apply the recurrence. The final answer is dp[0][n-1], the LPS of the entire string.
def longest_palindromic_subsequence(s):
n = len(s)
dp = [[0]*n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
for length in range(2, n+1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j]:
inner = dp[i+1][j-1] if length > 2 else 0
dp[i][j] = inner + 2
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
return dp[0][n-1]
print(longest_palindromic_subsequence('bbbab')) # 4LPS via LCS Equivalence
An elegant alternative: the LPS of string s equals the LCS of s and its reverse s[::-1]. This is because any palindromic subsequence of s is a common subsequence of s and its reverse. This reduction lets you reuse your LCS code directly. For 'bbbab' reversed is 'babbb', and their LCS is 4.
def lps_via_lcs(s):
t = s[::-1]
m, n = len(s), len(t)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if s[i-1] == t[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
print(lps_via_lcs('bbbab')) # 4Longest Palindromic Substring: Brute Force
The longest palindromic substring requires contiguous characters. A brute-force approach checks all O(n²) substrings and verifies each in O(n) time — O(n³) total. Two faster approaches exist: interval DP in O(n²) time and space, and expand-around-centre in O(n²) time but O(1) space. For interviews, expand-around-centre is preferred because it has a smaller constant and cleaner code.
Interval DP for Palindromic Substring
Define dp[i][j] = True if s[i..j] is a palindrome. Recurrence: dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]. Base cases: dp[i][i] = True and dp[i][i+1] = (s[i] == s[i+1]). Track the maximum length palindrome found. Fill in increasing length order. This runs in O(n²) time and O(n²) space.
def longest_palindrome_dp(s):
n = len(s)
dp = [[False]*n for _ in range(n)]
start, max_len = 0, 1
for i in range(n):
dp[i][i] = True
for i in range(n-1):
if s[i] == s[i+1]:
dp[i][i+1] = True
start, max_len = i, 2
for length in range(3, n+1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j] and dp[i+1][j-1]:
dp[i][j] = True
if length > max_len:
start, max_len = i, length
return s[start:start+max_len]
print(longest_palindrome_dp('babad')) # 'bab' or 'aba'Expand-Around-Centre Technique
The expand-around-centre approach tries each character (and each pair of adjacent characters) as a potential palindrome centre and expands outward as long as both sides match. There are 2n-1 possible centres (n odd-length, n-1 even-length). Each expansion takes at most O(n) time, giving O(n²) total with O(1) space — optimal for most interview settings.
def longest_palindrome_expand(s):
def expand(l, r):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1
r += 1
return r - l - 1 # length of palindrome
start, max_len = 0, 1
for i in range(len(s)):
odd = expand(i, i) # odd-length
even = expand(i, i+1) # even-length
best = max(odd, even)
if best > max_len:
max_len = best
start = i - (best - 1) // 2
return s[start:start+max_len]
print(longest_palindrome_expand('cbbd')) # 'bb'LPS Space Optimisation
The LPS interval DP uses O(n²) space. When you only need the length (not the actual subsequence), you can reduce space by observing that dp[i][j] only depends on dp[i+1][j-1], dp[i+1][j], and dp[i][j-1]. By reusing rows and saving one diagonal value, you can achieve O(n) space — though the implementation is more complex and rarely required in interviews.
Reconstructing the LPS
To reconstruct the actual palindromic subsequence, trace back through the DP table. Start at (0, n-1). If s[i] == s[j], add that character to both ends of your result and move to (i+1, j-1). Otherwise, move to whichever of (i+1, j) or (i, j-1) has the larger value. This greedy traceback uniquely recovers one optimal palindromic subsequence.
def reconstruct_lps(s, dp):
result = []
i, j = 0, len(s) - 1
while i < j:
if s[i] == s[j]:
result.append(s[i])
i += 1; j -= 1
elif dp[i+1][j] > dp[i][j-1]:
i += 1
else:
j -= 1
# middle character for odd-length
mid = [s[i]] if i == j else []
return ''.join(result + mid + result[::-1])
print('Traceback recovers one optimal LPS')Comparing LPS and LCS Time Complexity
Both LPS via interval DP and LCS run in O(n²) time and O(n²) space. The expand-around-centre for longest palindromic substring is O(n²) time but only O(1) space. Manacher's algorithm solves the substring problem in O(n) time and space, but it's complex enough that interviewers rarely expect it. For most interview contexts, expand-around-centre is the expected optimal solution for the substring variant.
Common Pitfalls and Edge Cases
Watch out for these pitfalls: (1) confusing subsequence with substring — they are different problems with different solutions; (2) the interval DP base case for length-2 intervals needs special handling since dp[i+1][j-1] would be dp[i+1][i] (empty interval); (3) for expand-around-centre, initialise max_len = 1 (every single character is a palindrome); and (4) when extracting the result, compute start = i - (best-1)//2 to correctly find the start index from the centre.
Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: LPS uses interval DP with recurrence dp[i][j] = dp[i+1][j-1]+2 when characters match, longest palindromic substring is best solved with expand-around-centre in O(n²) time and O(1) space, and LPS equals LCS of string and its reverse. Next up we tackle palindrome partitioning II, which combines a palindrome table with 1D DP for minimum cuts.
Frequently asked questions
Is the “Longest Palindromic Subsequence and Substring” lesson free?
Yes — the full text of “Longest Palindromic Subsequence and Substring” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “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. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 2 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Longest Palindromic Subsequence and Substring” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Interval DP Pattern and Fill Order
- Longest Palindromic Subsequence and Substring
- Palindrome Partitioning II
- Burst Balloons: Reverse Interval DP