What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

Theory Context•Dynamic Programming

Builds on Grid DP, which you haven’t finished yet.

P2MediumMental model~4 min speedrun

Interval DP (Longest Palindromic Subsequence)

Grows into

Burst Balloons Minimax DP

The problem

Longest Palindromic Subsequence (LC 516)(opens leetcode.com)

Given a string s, find the length of its longest palindromic subsequence. A subsequence keeps the letters of s in their original order but may skip any of them, so its letters do not have to sit next to each other. A palindrome reads the same from left to right and from right to left.

For example, the letters at positions 0, 1, 2 and 4 of "bbbab" form "bbbb", a palindrome of length 4, and no palindromic subsequence of that string is longer.

Return only the length, not the subsequence itself.

Example 1

Input:s = "bbbab"

Output:4

The letters at positions 0, 1, 2 and 4 form "bbbb". The a at position 3 is skipped.

Interval DP

range dp[i][j] ➔ built from shorter ranges inside it ➔ fill by increasing length

Spot it when: The answer for a stretch of one sequence is built from the answers for shorter stretches inside it, and the two ends of the stretch decide how: palindromes, merging, cutting or bursting items in a row.

Interval DP

Python

1	def longest_palindrome_subseq(s: str) -> int:
2	"""Longest Palindromic Subsequence: interval DP over the range s[i..j], filled from short ranges to long ones.
3	Time: O(N^2) \| Space: O(N^2)
4	"""
5	n = len(s)
6	# dp: dp[i][j] is the length of the longest palindromic subsequence of s[i..j]; one letter is a palindrome of length 1
7	dp = [[0] * n for _ in range(n)]
8	for i in range(n):
9	dp[i][i] = 1
10
11	# 1. Fill By Increasing Range Length:
12	# dp[i][j] reads dp[i + 1][j - 1], dp[i + 1][j] and dp[i][j - 1], all shorter ranges, so they must be final first.
13	for length in range(2, n + 1):
14	for i in range(n - length + 1):
15	j = i + length - 1
16	# 2. Match The Two Ends, Or Drop One:
17	# Equal end letters wrap the answer for the inside range with 2 more; otherwise one end cannot be used, so drop it.
18	if s[i] == s[j]:
19	dp[i][j] = dp[i + 1][j - 1] + 2
20	else:
21	dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
22
23	return dp[0][n - 1]

Invariant: After the loop finishes range length length, dp[i][j] is final for every range of that length or shorter.

Give every range s[i..j] one answer, dp[i][j], and build it only from shorter ranges inside it: when the two end letters match, they wrap the answer for the inside range dp[i + 1][j - 1] with 2 more; when they differ, one of them cannot be used, so take the better of dropping the left end (dp[i + 1][j]) or the right end (dp[i][j - 1]). Every shorter range is final before it is read, because the table is filled by increasing range length. The trap is the fill order: looping i upward row by row reads dp[i + 1][j - 1] while it is still 0, so fill by length, short ranges first.

See it run

Interval DP on "bbbab", step by step

length 1

Rows are the left end i and columns are the right end j, written as index:letter.

write the range being written
dp[i+1][j-1] the inside range, read when the two letters match
dp[i+1][j] the range without the left letter
dp[i][j-1] the range without the right letter
answer the final result

Every range of one letter is a palindrome of length 1. So dp[i][i] = 1 on the diagonal.

0:b

1:b

2:b

3:a

4:b

1 / 12

Gotchas1 of 3

The trap
Gotcha 1: Filling dp row by row from i = 0
Mistake
```
for i in range(n):
    for j in range(i + 1, n):
```
Fix
```
for length in range(2, n + 1):
    for i in range(n - length + 1):
        j = i + length - 1
```
What happens: dp[i][j] reads dp[i + 1][j - 1] and dp[i + 1][j], which belong to rows further down the table. A loop that runs i upward from 0 reads those cells while they are still 0, so the answer is too small. Fill by length, short ranges first, or run i from n - 1 down to 0.
Example: s = "bbbab"
Mistake: returns 2Fix: returns 4
Gotcha 2: Starting the one-letter ranges at 0
Mistake
```
dp[i][i] = 0
```
Fix
```
dp[i][i] = 1
```
What happens: One letter reads the same in both directions, so the longest palindromic subsequence of a one-letter range has length 1. With 0 as the base, a string with no matching letters gets the answer 0 instead of 1, and every other answer is built on cells that are too small.
Example: s = "abc"
Mistake: returns 0Fix: returns 1
Gotcha 3: Dropping both ends on a mismatch
Mistake
```
dp[i][j] = dp[i + 1][j - 1]
```
Fix
```
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
```
What happens: When the two end letters differ, they cannot both be used, but one of them may still belong to the best answer. Taking the range without both letters throws that letter away. Take the better of dropping only the left end or only the right end.
Example: s = "bbbab"
Mistake: returns 3Fix: returns 4

Not this one if…

Two different strings are compared prefix by prefix, as in Edit Distance (LC 72): each cell comes from the cell above, to the left or diagonal, and there is no single range with two ends. See Two-Sequence DP
The letters must stay next to each other, as in Longest Palindromic Substring (LC 5): grow a palindrome from each centre instead of filling a table of ranges. See Longest Palindromic Substring

Deep Dive

What a state is: one range of the sequence

A range is the part of s from position i to position j, written s[i..j]. In Interval DP, dp[i][j] is the answer for exactly that range.

In Longest Palindromic Subsequence (LC 516), dp[i][j] is the length of the longest palindromic subsequence of s[i..j]. A palindromic subsequence reads the same forwards and backwards, and its letters may be taken from any positions in order.

A range of one letter is a palindrome of length 1, so dp[i][i] = 1. The answer for the whole string is the answer for the largest range, dp[0][n - 1].

Example: for s = "bbbab", the table row dp[0] is [1, 2, 3, 3, 4]. So dp[0][4] = 4, and the palindrome is "bbbb".

Why the two end letters decide the recurrence

Look at s[i] and s[j], the two ends of the range. If they are equal, an optimal palindrome can use both as its outer letters. What remains is the best palindrome inside, dp[i + 1][j - 1], so dp[i][j] = dp[i + 1][j - 1] + 2.

If they differ, no palindrome can use both ends as its outer letters. So at least one end is not used. The answer is the better of dropping the left end, dp[i + 1][j], and dropping the right end, dp[i][j - 1].

Every case reads only ranges that are shorter than (i, j). This is the property that makes a table of ranges possible.

When length is 2, the inside range is empty. The code reads dp[i + 1][j - 1] from a cell that is never written, so it is 0. That is the correct length for an empty range. For s = "aa" this gives 0 + 2 = 2.

Why the fill order is by length

dp[i][j] reads dp[i + 1][j - 1], dp[i + 1][j] and dp[i][j - 1]. All of them are ranges shorter than j - i + 1. So every shorter range must be final before a longer range is computed.

The loop for length in range(2, n + 1) fills ranges of length 2 first, then 3, up to n. The invariant of the card says the same: after length length is done, every range of that length or shorter is final.

A loop that goes row by row from i = 0 reads rows below it that are still 0. For s = "bbbab" it returns 2 instead of 4. Running i from n - 1 down to 0 is also correct, because the rows below are then final.

The cost: ranges times work per range

The card's complexity line is O(N^2) time and O(N^2) space. There are N * (N + 1) / 2 ranges, and each one does constant work: one comparison and one max.

For n = 1000, the loops fill 499,500 cells with length 2 or more, and dp has 1,000,000 cells. LeetCode limits s to 1000 characters, so this fits.

Each row dp[i] reads only row i and row i + 1. If you run i downward, you can keep one row and a saved previous value, and the space becomes O(N). The time stays O(N^2).

This answer equals the longest common subsequence of s and s reversed, as in Longest Common Subsequence (LC 1143). The range table needs one string and is the better start for problems that ask to cut, merge or burst items inside a range.

60-Second Pitch

"I give every range s[i..j] one answer, dp[i][j]: the length of the longest palindromic subsequence in it. If the two end letters are equal, they wrap the answer for the inside range, so I add 2. If they differ, one end is not used, so I take the better of dropping the left end and dropping the right end. Each range reads only shorter ranges, so I fill the table by increasing length. One-letter ranges start at 1. There are about N squared over 2 ranges with constant work each. That is O(N^2) time and O(N^2) space, and I can reduce the space to O(N) with one row."

Common Questions

Why is the fill order by length and not row by row?: Each cell reads ranges shorter than itself, and some of them are in rows further down. Filling by length makes every shorter range final first. Filling row by row from i = 0 reads zeros, and "bbbab" returns 2 instead of 4. Running i from n - 1 down to 0 also works.
What is the time and space complexity, and can the space be smaller?: O(N^2) time and O(N^2) space. There are about N^2 / 2 ranges and each does constant work. With i running downward, a cell needs only the current row and the previous row, so one row and one saved value give O(N) space.
How is this related to Longest Common Subsequence (LC 1143)?: The longest palindromic subsequence of s has the same length as the longest common subsequence of s and its reverse. Both take O(N^2) time. The range table is the method that also works when the problem removes or merges items inside a range.
How would you rebuild the palindrome and not only its length?: Start at (0, n - 1). If s[i] == s[j], take that letter and move to (i + 1, j - 1). Otherwise move to the neighbour range with the larger value: (i + 1, j) or (i, j - 1). Collect the letters from the outside in, and mirror them.
Can this be solved with memoization?: Yes. Write solve(i, j) with the same three cases and cache it by (i, j). The depth is at most N, so for N up to 1000 you may need a higher recursion limit or the loop version. The time is still O(N^2).

SWE Reasoning

Spot it

The input is one sequence, and the question is about a stretch of it: the best palindrome, the cheapest merge, the best way to cut.
The answer for a stretch comes from the answers for shorter stretches inside it. The two ends of the stretch decide how.
The brute force tries subsets or orders. That is exponential, but the number of different ranges is only about N^2 / 2.
Prefix tables do not fit, because the sub-problem needs both a left end and a right end.
N is up to about 1000 for O(N^2), or a few hundred when each range also tries a split point.

The invariant, step by step

Set n = len(s). Create dp with n rows and n columns, all 0. Then set dp[i][i] = 1 for every i, because one letter is a palindrome.
The loop sets length to 2, then 3, up to n. Every range shorter than length is already final.
For each i, the code sets j = i + length - 1. This is the range s[i..j].
If s[i] == s[j], both letters wrap the best palindrome of the inside range. The code writes dp[i][j] = dp[i + 1][j - 1] + 2.
If the letters differ, one end cannot be used. The code writes dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]).
After the last length, dp[0][n - 1] is final for the whole string, and the function returns it.

Traps

Wrong fill order. Looping i upward row by row reads cells that are still 0. For "bbbab" the result is 2 instead of 4.
Base value 0. With dp[i][i] = 0, the string "abc" returns 0 instead of 1.
Dropping both ends on a mismatch. dp[i][j] = dp[i + 1][j - 1] throws away a letter that may belong to the best answer. For "bbbab" it returns 3 instead of 4.
Confusing subsequence with substring. In Longest Palindromic Substring (LC 5) the letters must be next to each other. Here they may be far apart. For "cbbd", both versions give 2, but for "bbbab" the substring answer is 3 and the subsequence answer is 4.
Empty input. For s = "", dp[0][n - 1] raises IndexError. LeetCode guarantees at least one letter. In your own code, return 0 first.

Practice

Canonical LeetCode:Longest Palindromic Subsequence (LC 516)Valid Palindrome III (LC 1216)Minimum Insertion Steps to Make a String Palindrome (LC 1312)

Theory Context•Dynamic Programming

Builds on Grid DP, which you haven’t finished yet.

P2MediumMental model~4 min speedrun

Interval DP (Longest Palindromic Subsequence)

Grows into

Burst Balloons Minimax DP

The problem

Longest Palindromic Subsequence (LC 516)(opens leetcode.com)

For example, the letters at positions 0, 1, 2 and 4 of "bbbab" form "bbbb", a palindrome of length 4, and no palindromic subsequence of that string is longer.

Return only the length, not the subsequence itself.

Example 1

Input:s = "bbbab"

Output:4

The letters at positions 0, 1, 2 and 4 form "bbbb". The a at position 3 is skipped.

Interval DP

range dp[i][j] ➔ built from shorter ranges inside it ➔ fill by increasing length

Interval DP

Python

1	def longest_palindrome_subseq(s: str) -> int:
2	"""Longest Palindromic Subsequence: interval DP over the range s[i..j], filled from short ranges to long ones.
3	Time: O(N^2) \| Space: O(N^2)
4	"""
5	n = len(s)
6	# dp: dp[i][j] is the length of the longest palindromic subsequence of s[i..j]; one letter is a palindrome of length 1
7	dp = [[0] * n for _ in range(n)]
8	for i in range(n):
9	dp[i][i] = 1
10
11	# 1. Fill By Increasing Range Length:
12	# dp[i][j] reads dp[i + 1][j - 1], dp[i + 1][j] and dp[i][j - 1], all shorter ranges, so they must be final first.
13	for length in range(2, n + 1):
14	for i in range(n - length + 1):
15	j = i + length - 1
16	# 2. Match The Two Ends, Or Drop One:
17	# Equal end letters wrap the answer for the inside range with 2 more; otherwise one end cannot be used, so drop it.
18	if s[i] == s[j]:
19	dp[i][j] = dp[i + 1][j - 1] + 2
20	else:
21	dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
22
23	return dp[0][n - 1]

Invariant: After the loop finishes range length length, dp[i][j] is final for every range of that length or shorter.

See it run

Interval DP on "bbbab", step by step

length 1

Rows are the left end i and columns are the right end j, written as index:letter.

write the range being written
dp[i+1][j-1] the inside range, read when the two letters match
dp[i+1][j] the range without the left letter
dp[i][j-1] the range without the right letter
answer the final result

Every range of one letter is a palindrome of length 1. So dp[i][i] = 1 on the diagonal.

0:b

1:b

2:b

3:a

4:b

1 / 12

Gotchas1 of 3

The trap
Gotcha 1: Filling dp row by row from i = 0
Mistake
```
for i in range(n):
    for j in range(i + 1, n):
```
Fix
```
for length in range(2, n + 1):
    for i in range(n - length + 1):
        j = i + length - 1
```
What happens: dp[i][j] reads dp[i + 1][j - 1] and dp[i + 1][j], which belong to rows further down the table. A loop that runs i upward from 0 reads those cells while they are still 0, so the answer is too small. Fill by length, short ranges first, or run i from n - 1 down to 0.
Example: s = "bbbab"
Mistake: returns 2Fix: returns 4
Gotcha 2: Starting the one-letter ranges at 0
Mistake
```
dp[i][i] = 0
```
Fix
```
dp[i][i] = 1
```
What happens: One letter reads the same in both directions, so the longest palindromic subsequence of a one-letter range has length 1. With 0 as the base, a string with no matching letters gets the answer 0 instead of 1, and every other answer is built on cells that are too small.
Example: s = "abc"
Mistake: returns 0Fix: returns 1
Gotcha 3: Dropping both ends on a mismatch
Mistake
```
dp[i][j] = dp[i + 1][j - 1]
```
Fix
```
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
```
What happens: When the two end letters differ, they cannot both be used, but one of them may still belong to the best answer. Taking the range without both letters throws that letter away. Take the better of dropping only the left end or only the right end.
Example: s = "bbbab"
Mistake: returns 3Fix: returns 4

Not this one if…

Two different strings are compared prefix by prefix, as in Edit Distance (LC 72): each cell comes from the cell above, to the left or diagonal, and there is no single range with two ends. See Two-Sequence DP
The letters must stay next to each other, as in Longest Palindromic Substring (LC 5): grow a palindrome from each centre instead of filling a table of ranges. See Longest Palindromic Substring

Deep Dive

What a state is: one range of the sequence

A range is the part of s from position i to position j, written s[i..j]. In Interval DP, dp[i][j] is the answer for exactly that range.

A range of one letter is a palindrome of length 1, so dp[i][i] = 1. The answer for the whole string is the answer for the largest range, dp[0][n - 1].

Example: for s = "bbbab", the table row dp[0] is [1, 2, 3, 3, 4]. So dp[0][4] = 4, and the palindrome is "bbbb".

Why the two end letters decide the recurrence

Every case reads only ranges that are shorter than (i, j). This is the property that makes a table of ranges possible.

Why the fill order is by length

dp[i][j] reads dp[i + 1][j - 1], dp[i + 1][j] and dp[i][j - 1]. All of them are ranges shorter than j - i + 1. So every shorter range must be final before a longer range is computed.

The cost: ranges times work per range

The card's complexity line is O(N^2) time and O(N^2) space. There are N * (N + 1) / 2 ranges, and each one does constant work: one comparison and one max.

For n = 1000, the loops fill 499,500 cells with length 2 or more, and dp has 1,000,000 cells. LeetCode limits s to 1000 characters, so this fits.

Each row dp[i] reads only row i and row i + 1. If you run i downward, you can keep one row and a saved previous value, and the space becomes O(N). The time stays O(N^2).

60-Second Pitch

Common Questions

Why is the fill order by length and not row by row?: Each cell reads ranges shorter than itself, and some of them are in rows further down. Filling by length makes every shorter range final first. Filling row by row from i = 0 reads zeros, and "bbbab" returns 2 instead of 4. Running i from n - 1 down to 0 also works.
What is the time and space complexity, and can the space be smaller?: O(N^2) time and O(N^2) space. There are about N^2 / 2 ranges and each does constant work. With i running downward, a cell needs only the current row and the previous row, so one row and one saved value give O(N) space.
How is this related to Longest Common Subsequence (LC 1143)?: The longest palindromic subsequence of s has the same length as the longest common subsequence of s and its reverse. Both take O(N^2) time. The range table is the method that also works when the problem removes or merges items inside a range.
How would you rebuild the palindrome and not only its length?: Start at (0, n - 1). If s[i] == s[j], take that letter and move to (i + 1, j - 1). Otherwise move to the neighbour range with the larger value: (i + 1, j) or (i, j - 1). Collect the letters from the outside in, and mirror them.
Can this be solved with memoization?: Yes. Write solve(i, j) with the same three cases and cache it by (i, j). The depth is at most N, so for N up to 1000 you may need a higher recursion limit or the loop version. The time is still O(N^2).

SWE Reasoning

Spot it

The input is one sequence, and the question is about a stretch of it: the best palindrome, the cheapest merge, the best way to cut.
The answer for a stretch comes from the answers for shorter stretches inside it. The two ends of the stretch decide how.
The brute force tries subsets or orders. That is exponential, but the number of different ranges is only about N^2 / 2.
Prefix tables do not fit, because the sub-problem needs both a left end and a right end.
N is up to about 1000 for O(N^2), or a few hundred when each range also tries a split point.

The invariant, step by step

Set n = len(s). Create dp with n rows and n columns, all 0. Then set dp[i][i] = 1 for every i, because one letter is a palindrome.
The loop sets length to 2, then 3, up to n. Every range shorter than length is already final.
For each i, the code sets j = i + length - 1. This is the range s[i..j].
If s[i] == s[j], both letters wrap the best palindrome of the inside range. The code writes dp[i][j] = dp[i + 1][j - 1] + 2.
If the letters differ, one end cannot be used. The code writes dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]).
After the last length, dp[0][n - 1] is final for the whole string, and the function returns it.

Traps

Wrong fill order. Looping i upward row by row reads cells that are still 0. For "bbbab" the result is 2 instead of 4.
Base value 0. With dp[i][i] = 0, the string "abc" returns 0 instead of 1.
Dropping both ends on a mismatch. dp[i][j] = dp[i + 1][j - 1] throws away a letter that may belong to the best answer. For "bbbab" it returns 3 instead of 4.
Confusing subsequence with substring. In Longest Palindromic Substring (LC 5) the letters must be next to each other. Here they may be far apart. For "cbbd", both versions give 2, but for "bbbab" the substring answer is 3 and the subsequence answer is 4.
Empty input. For s = "", dp[0][n - 1] raises IndexError. LeetCode guarantees at least one letter. In your own code, return 0 first.

Practice

Canonical LeetCode:Longest Palindromic Subsequence (LC 516)Valid Palindrome III (LC 1216)Minimum Insertion Steps to Make a String Palindrome (LC 1312)

Theory Context•Dynamic Programming

Builds on Grid DP, which you haven’t finished yet.

P2MediumMental model~4 min speedrun

Interval DP (Longest Palindromic Subsequence)

Grows into

Burst Balloons Minimax DP

The problem

Longest Palindromic Subsequence (LC 516)(opens leetcode.com)

For example, the letters at positions 0, 1, 2 and 4 of "bbbab" form "bbbb", a palindrome of length 4, and no palindromic subsequence of that string is longer.

Return only the length, not the subsequence itself.

Example 1

Input:s = "bbbab"

Output:4

The letters at positions 0, 1, 2 and 4 form "bbbb". The a at position 3 is skipped.

Interval DP

range dp[i][j] ➔ built from shorter ranges inside it ➔ fill by increasing length

Interval DP

Python

1	def longest_palindrome_subseq(s: str) -> int:
2	"""Longest Palindromic Subsequence: interval DP over the range s[i..j], filled from short ranges to long ones.
3	Time: O(N^2) \| Space: O(N^2)
4	"""
5	n = len(s)
6	# dp: dp[i][j] is the length of the longest palindromic subsequence of s[i..j]; one letter is a palindrome of length 1
7	dp = [[0] * n for _ in range(n)]
8	for i in range(n):
9	dp[i][i] = 1
10
11	# 1. Fill By Increasing Range Length:
12	# dp[i][j] reads dp[i + 1][j - 1], dp[i + 1][j] and dp[i][j - 1], all shorter ranges, so they must be final first.
13	for length in range(2, n + 1):
14	for i in range(n - length + 1):
15	j = i + length - 1
16	# 2. Match The Two Ends, Or Drop One:
17	# Equal end letters wrap the answer for the inside range with 2 more; otherwise one end cannot be used, so drop it.
18	if s[i] == s[j]:
19	dp[i][j] = dp[i + 1][j - 1] + 2
20	else:
21	dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
22
23	return dp[0][n - 1]

Invariant: After the loop finishes range length length, dp[i][j] is final for every range of that length or shorter.

See it run

Interval DP on "bbbab", step by step

length 1

Rows are the left end i and columns are the right end j, written as index:letter.

write the range being written
dp[i+1][j-1] the inside range, read when the two letters match
dp[i+1][j] the range without the left letter
dp[i][j-1] the range without the right letter
answer the final result

Every range of one letter is a palindrome of length 1. So dp[i][i] = 1 on the diagonal.

0:b

1:b

2:b

3:a

4:b

1 / 12

Gotchas1 of 3

The trap
Gotcha 1: Filling dp row by row from i = 0
Mistake
```
for i in range(n):
    for j in range(i + 1, n):
```
Fix
```
for length in range(2, n + 1):
    for i in range(n - length + 1):
        j = i + length - 1
```
What happens: dp[i][j] reads dp[i + 1][j - 1] and dp[i + 1][j], which belong to rows further down the table. A loop that runs i upward from 0 reads those cells while they are still 0, so the answer is too small. Fill by length, short ranges first, or run i from n - 1 down to 0.
Example: s = "bbbab"
Mistake: returns 2Fix: returns 4
Gotcha 2: Starting the one-letter ranges at 0
Mistake
```
dp[i][i] = 0
```
Fix
```
dp[i][i] = 1
```
What happens: One letter reads the same in both directions, so the longest palindromic subsequence of a one-letter range has length 1. With 0 as the base, a string with no matching letters gets the answer 0 instead of 1, and every other answer is built on cells that are too small.
Example: s = "abc"
Mistake: returns 0Fix: returns 1
Gotcha 3: Dropping both ends on a mismatch
Mistake
```
dp[i][j] = dp[i + 1][j - 1]
```
Fix
```
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
```
What happens: When the two end letters differ, they cannot both be used, but one of them may still belong to the best answer. Taking the range without both letters throws that letter away. Take the better of dropping only the left end or only the right end.
Example: s = "bbbab"
Mistake: returns 3Fix: returns 4

Not this one if…

Two different strings are compared prefix by prefix, as in Edit Distance (LC 72): each cell comes from the cell above, to the left or diagonal, and there is no single range with two ends. See Two-Sequence DP
The letters must stay next to each other, as in Longest Palindromic Substring (LC 5): grow a palindrome from each centre instead of filling a table of ranges. See Longest Palindromic Substring

Deep Dive

What a state is: one range of the sequence

A range is the part of s from position i to position j, written s[i..j]. In Interval DP, dp[i][j] is the answer for exactly that range.

A range of one letter is a palindrome of length 1, so dp[i][i] = 1. The answer for the whole string is the answer for the largest range, dp[0][n - 1].

Example: for s = "bbbab", the table row dp[0] is [1, 2, 3, 3, 4]. So dp[0][4] = 4, and the palindrome is "bbbb".

Why the two end letters decide the recurrence

Every case reads only ranges that are shorter than (i, j). This is the property that makes a table of ranges possible.

Why the fill order is by length

dp[i][j] reads dp[i + 1][j - 1], dp[i + 1][j] and dp[i][j - 1]. All of them are ranges shorter than j - i + 1. So every shorter range must be final before a longer range is computed.

The cost: ranges times work per range

The card's complexity line is O(N^2) time and O(N^2) space. There are N * (N + 1) / 2 ranges, and each one does constant work: one comparison and one max.

For n = 1000, the loops fill 499,500 cells with length 2 or more, and dp has 1,000,000 cells. LeetCode limits s to 1000 characters, so this fits.

Each row dp[i] reads only row i and row i + 1. If you run i downward, you can keep one row and a saved previous value, and the space becomes O(N). The time stays O(N^2).

60-Second Pitch

Common Questions

Why is the fill order by length and not row by row?: Each cell reads ranges shorter than itself, and some of them are in rows further down. Filling by length makes every shorter range final first. Filling row by row from i = 0 reads zeros, and "bbbab" returns 2 instead of 4. Running i from n - 1 down to 0 also works.
What is the time and space complexity, and can the space be smaller?: O(N^2) time and O(N^2) space. There are about N^2 / 2 ranges and each does constant work. With i running downward, a cell needs only the current row and the previous row, so one row and one saved value give O(N) space.
How is this related to Longest Common Subsequence (LC 1143)?: The longest palindromic subsequence of s has the same length as the longest common subsequence of s and its reverse. Both take O(N^2) time. The range table is the method that also works when the problem removes or merges items inside a range.
How would you rebuild the palindrome and not only its length?: Start at (0, n - 1). If s[i] == s[j], take that letter and move to (i + 1, j - 1). Otherwise move to the neighbour range with the larger value: (i + 1, j) or (i, j - 1). Collect the letters from the outside in, and mirror them.
Can this be solved with memoization?: Yes. Write solve(i, j) with the same three cases and cache it by (i, j). The depth is at most N, so for N up to 1000 you may need a higher recursion limit or the loop version. The time is still O(N^2).

SWE Reasoning

Spot it

The input is one sequence, and the question is about a stretch of it: the best palindrome, the cheapest merge, the best way to cut.
The answer for a stretch comes from the answers for shorter stretches inside it. The two ends of the stretch decide how.
The brute force tries subsets or orders. That is exponential, but the number of different ranges is only about N^2 / 2.
Prefix tables do not fit, because the sub-problem needs both a left end and a right end.
N is up to about 1000 for O(N^2), or a few hundred when each range also tries a split point.

The invariant, step by step

Set n = len(s). Create dp with n rows and n columns, all 0. Then set dp[i][i] = 1 for every i, because one letter is a palindrome.
The loop sets length to 2, then 3, up to n. Every range shorter than length is already final.
For each i, the code sets j = i + length - 1. This is the range s[i..j].
If s[i] == s[j], both letters wrap the best palindrome of the inside range. The code writes dp[i][j] = dp[i + 1][j - 1] + 2.
If the letters differ, one end cannot be used. The code writes dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]).
After the last length, dp[0][n - 1] is final for the whole string, and the function returns it.

Traps

Wrong fill order. Looping i upward row by row reads cells that are still 0. For "bbbab" the result is 2 instead of 4.
Base value 0. With dp[i][i] = 0, the string "abc" returns 0 instead of 1.
Dropping both ends on a mismatch. dp[i][j] = dp[i + 1][j - 1] throws away a letter that may belong to the best answer. For "bbbab" it returns 3 instead of 4.
Confusing subsequence with substring. In Longest Palindromic Substring (LC 5) the letters must be next to each other. Here they may be far apart. For "cbbd", both versions give 2, but for "bbbab" the substring answer is 3 and the subsequence answer is 4.
Empty input. For s = "", dp[0][n - 1] raises IndexError. LeetCode guarantees at least one letter. In your own code, return 0 first.

Practice

Canonical LeetCode:Longest Palindromic Subsequence (LC 516)Valid Palindrome III (LC 1216)Minimum Insertion Steps to Make a String Palindrome (LC 1312)

Theory Context•Dynamic Programming

Builds on Grid DP, which you haven’t finished yet.

P2MediumMental model~4 min speedrun

Interval DP (Longest Palindromic Subsequence)

Grows into

Burst Balloons Minimax DP

The problem

Longest Palindromic Subsequence (LC 516)(opens leetcode.com)

For example, the letters at positions 0, 1, 2 and 4 of "bbbab" form "bbbb", a palindrome of length 4, and no palindromic subsequence of that string is longer.

Return only the length, not the subsequence itself.

Example 1

Input:s = "bbbab"

Output:4

The letters at positions 0, 1, 2 and 4 form "bbbb". The a at position 3 is skipped.

Interval DP

range dp[i][j] ➔ built from shorter ranges inside it ➔ fill by increasing length

Interval DP

Python

1	def longest_palindrome_subseq(s: str) -> int:
2	"""Longest Palindromic Subsequence: interval DP over the range s[i..j], filled from short ranges to long ones.
3	Time: O(N^2) \| Space: O(N^2)
4	"""
5	n = len(s)
6	# dp: dp[i][j] is the length of the longest palindromic subsequence of s[i..j]; one letter is a palindrome of length 1
7	dp = [[0] * n for _ in range(n)]
8	for i in range(n):
9	dp[i][i] = 1
10
11	# 1. Fill By Increasing Range Length:
12	# dp[i][j] reads dp[i + 1][j - 1], dp[i + 1][j] and dp[i][j - 1], all shorter ranges, so they must be final first.
13	for length in range(2, n + 1):
14	for i in range(n - length + 1):
15	j = i + length - 1
16	# 2. Match The Two Ends, Or Drop One:
17	# Equal end letters wrap the answer for the inside range with 2 more; otherwise one end cannot be used, so drop it.
18	if s[i] == s[j]:
19	dp[i][j] = dp[i + 1][j - 1] + 2
20	else:
21	dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
22
23	return dp[0][n - 1]

Invariant: After the loop finishes range length length, dp[i][j] is final for every range of that length or shorter.

See it run

Interval DP on "bbbab", step by step

length 1

Rows are the left end i and columns are the right end j, written as index:letter.

write the range being written
dp[i+1][j-1] the inside range, read when the two letters match
dp[i+1][j] the range without the left letter
dp[i][j-1] the range without the right letter
answer the final result

Every range of one letter is a palindrome of length 1. So dp[i][i] = 1 on the diagonal.

0:b

1:b

2:b

3:a

4:b

1 / 12

Gotchas1 of 3

The trap
Gotcha 1: Filling dp row by row from i = 0
Mistake
```
for i in range(n):
    for j in range(i + 1, n):
```
Fix
```
for length in range(2, n + 1):
    for i in range(n - length + 1):
        j = i + length - 1
```
What happens: dp[i][j] reads dp[i + 1][j - 1] and dp[i + 1][j], which belong to rows further down the table. A loop that runs i upward from 0 reads those cells while they are still 0, so the answer is too small. Fill by length, short ranges first, or run i from n - 1 down to 0.
Example: s = "bbbab"
Mistake: returns 2Fix: returns 4
Gotcha 2: Starting the one-letter ranges at 0
Mistake
```
dp[i][i] = 0
```
Fix
```
dp[i][i] = 1
```
What happens: One letter reads the same in both directions, so the longest palindromic subsequence of a one-letter range has length 1. With 0 as the base, a string with no matching letters gets the answer 0 instead of 1, and every other answer is built on cells that are too small.
Example: s = "abc"
Mistake: returns 0Fix: returns 1
Gotcha 3: Dropping both ends on a mismatch
Mistake
```
dp[i][j] = dp[i + 1][j - 1]
```
Fix
```
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
```
What happens: When the two end letters differ, they cannot both be used, but one of them may still belong to the best answer. Taking the range without both letters throws that letter away. Take the better of dropping only the left end or only the right end.
Example: s = "bbbab"
Mistake: returns 3Fix: returns 4

Not this one if…

Two different strings are compared prefix by prefix, as in Edit Distance (LC 72): each cell comes from the cell above, to the left or diagonal, and there is no single range with two ends. See Two-Sequence DP
The letters must stay next to each other, as in Longest Palindromic Substring (LC 5): grow a palindrome from each centre instead of filling a table of ranges. See Longest Palindromic Substring

Deep Dive

What a state is: one range of the sequence

A range is the part of s from position i to position j, written s[i..j]. In Interval DP, dp[i][j] is the answer for exactly that range.

A range of one letter is a palindrome of length 1, so dp[i][i] = 1. The answer for the whole string is the answer for the largest range, dp[0][n - 1].

Example: for s = "bbbab", the table row dp[0] is [1, 2, 3, 3, 4]. So dp[0][4] = 4, and the palindrome is "bbbb".

Why the two end letters decide the recurrence

Every case reads only ranges that are shorter than (i, j). This is the property that makes a table of ranges possible.

Why the fill order is by length

dp[i][j] reads dp[i + 1][j - 1], dp[i + 1][j] and dp[i][j - 1]. All of them are ranges shorter than j - i + 1. So every shorter range must be final before a longer range is computed.

The cost: ranges times work per range

The card's complexity line is O(N^2) time and O(N^2) space. There are N * (N + 1) / 2 ranges, and each one does constant work: one comparison and one max.

For n = 1000, the loops fill 499,500 cells with length 2 or more, and dp has 1,000,000 cells. LeetCode limits s to 1000 characters, so this fits.

Each row dp[i] reads only row i and row i + 1. If you run i downward, you can keep one row and a saved previous value, and the space becomes O(N). The time stays O(N^2).

60-Second Pitch

Common Questions

Why is the fill order by length and not row by row?: Each cell reads ranges shorter than itself, and some of them are in rows further down. Filling by length makes every shorter range final first. Filling row by row from i = 0 reads zeros, and "bbbab" returns 2 instead of 4. Running i from n - 1 down to 0 also works.
What is the time and space complexity, and can the space be smaller?: O(N^2) time and O(N^2) space. There are about N^2 / 2 ranges and each does constant work. With i running downward, a cell needs only the current row and the previous row, so one row and one saved value give O(N) space.
How is this related to Longest Common Subsequence (LC 1143)?: The longest palindromic subsequence of s has the same length as the longest common subsequence of s and its reverse. Both take O(N^2) time. The range table is the method that also works when the problem removes or merges items inside a range.
How would you rebuild the palindrome and not only its length?: Start at (0, n - 1). If s[i] == s[j], take that letter and move to (i + 1, j - 1). Otherwise move to the neighbour range with the larger value: (i + 1, j) or (i, j - 1). Collect the letters from the outside in, and mirror them.
Can this be solved with memoization?: Yes. Write solve(i, j) with the same three cases and cache it by (i, j). The depth is at most N, so for N up to 1000 you may need a higher recursion limit or the loop version. The time is still O(N^2).

SWE Reasoning

Spot it

The input is one sequence, and the question is about a stretch of it: the best palindrome, the cheapest merge, the best way to cut.
The answer for a stretch comes from the answers for shorter stretches inside it. The two ends of the stretch decide how.
The brute force tries subsets or orders. That is exponential, but the number of different ranges is only about N^2 / 2.
Prefix tables do not fit, because the sub-problem needs both a left end and a right end.
N is up to about 1000 for O(N^2), or a few hundred when each range also tries a split point.

The invariant, step by step

Set n = len(s). Create dp with n rows and n columns, all 0. Then set dp[i][i] = 1 for every i, because one letter is a palindrome.
The loop sets length to 2, then 3, up to n. Every range shorter than length is already final.
For each i, the code sets j = i + length - 1. This is the range s[i..j].
If s[i] == s[j], both letters wrap the best palindrome of the inside range. The code writes dp[i][j] = dp[i + 1][j - 1] + 2.
If the letters differ, one end cannot be used. The code writes dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]).
After the last length, dp[0][n - 1] is final for the whole string, and the function returns it.

Traps

Wrong fill order. Looping i upward row by row reads cells that are still 0. For "bbbab" the result is 2 instead of 4.
Base value 0. With dp[i][i] = 0, the string "abc" returns 0 instead of 1.
Dropping both ends on a mismatch. dp[i][j] = dp[i + 1][j - 1] throws away a letter that may belong to the best answer. For "bbbab" it returns 3 instead of 4.
Confusing subsequence with substring. In Longest Palindromic Substring (LC 5) the letters must be next to each other. Here they may be far apart. For "cbbd", both versions give 2, but for "bbbab" the substring answer is 3 and the subsequence answer is 4.
Empty input. For s = "", dp[0][n - 1] raises IndexError. LeetCode guarantees at least one letter. In your own code, return 0 first.

Practice

Canonical LeetCode:Longest Palindromic Subsequence (LC 516)Valid Palindrome III (LC 1216)Minimum Insertion Steps to Make a String Palindrome (LC 1312)