Palindrome and Interval DP
30 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Some tables are indexed by a range i to j of a sequence, not by a prefix. Short ranges are solved first and longer ones are built from them, so the loop runs over the length of the range.
Palindromic substrings
A palindrome reads the same forwards and backwards. Let pal[i][j] be True when s[i..j] is a palindrome. It is, when the two end letters match and the inside s[i + 1..j - 1] is a palindrome. Short ranges come first.
def longest_palindrome(s): n = len(s) pal = [[False] * n for _ in range(n)] best = s[:1] for length in range(1, n + 1): for i in range(n - length + 1): j = i + length - 1 if s[i] == s[j] and (length <= 2 or pal[i + 1][j - 1]): pal[i][j] = True if length > len(best): best = s[i:j + 1] return bestExample 1 · Expand around each centre
def longest_palindrome(s): best = "" for centre in range(len(s)): for left, right in ((centre, centre), (centre, centre + 1)): while left >= 0 and right < len(s) and s[left] == s[right]: left -= 1 right += 1 if right - left - 1 > len(best): best = s[left + 1:right] return best
print(longest_palindrome("babad"))print(longest_palindrome("cbbd"))bab bb
What this code does
- Every palindrome grows from a centre, one letter (odd length) or two letters (even length). Stretch outwards while the ends match.
- This is O(n squared) time and O(1) extra space, which is the answer an interviewer often prefers over the table.
Example 2 · The table version
def longest_palindrome(s): n = len(s) pal = [[False] * n for _ in range(n)] best = s[:1] for length in range(1, n + 1): for i in range(n - length + 1): j = i + length - 1 if s[i] == s[j] and (length <= 2 or pal[i + 1][j - 1]): pal[i][j] = True if length > len(best): best = s[i:j + 1] return best
print(longest_palindrome("forgeeksskeegfor"))geeksskeeg
What this code does
- pal[i][j] is filled for short ranges first, so the inside range is always ready.
- The longest palindrome in the text is "geeksskeeg".
Example 3 · Count every palindromic substring
def count_palindromes(s): n = len(s) pal = [[False] * n for _ in range(n)] count = 0 for length in range(1, n + 1): for i in range(n - length + 1): j = i + length - 1 if s[i] == s[j] and (length <= 2 or pal[i + 1][j - 1]): pal[i][j] = True count += 1 return count
print(count_palindromes("aaa"), count_palindromes("abc"))6 3
What this code does
- "aaa" has a, a, a, aa, aa and aaa, so 6 palindromic substrings. Equal positions with different ranges count separately.
- "abc" has only its three single letters.
Ranges of length 1 and 2 need no inside check. Every longer range looks at one shorter range, so the table is O(n squared) time and space.
Palindromic subsequence
Now letters may be skipped. lps[i][j] is the longest palindromic subsequence inside s[i..j]. If the end letters match, they wrap the best inside answer, adding 2. Otherwise drop one end letter and keep the better result.
def longest_pal_subseq(s): n = len(s) lps = [[0] * n for _ in range(n)] for i in range(n - 1, -1, -1): lps[i][i] = 1 for j in range(i + 1, n): if s[i] == s[j]: lps[i][j] = lps[i + 1][j - 1] + 2 else: lps[i][j] = max(lps[i + 1][j], lps[i][j - 1]) return lps[0][n - 1] if n else 0Example 4 · Longest palindromic subsequence
def longest_pal_subseq(s): n = len(s) lps = [[0] * n for _ in range(n)] for i in range(n - 1, -1, -1): lps[i][i] = 1 for j in range(i + 1, n): if s[i] == s[j]: lps[i][j] = lps[i + 1][j - 1] + 2 else: lps[i][j] = max(lps[i + 1][j], lps[i][j - 1]) return lps[0][n - 1] if n else 0
print(longest_pal_subseq("agbcba"))print(longest_pal_subseq("abcd"))5 1
What this code does
- "agbcba" contains the subsequence "abcba" of length 5. Skipping g gives it.
- No letter repeats in "abcd", so the best is a single letter.
Example 5 · Python shortcut: compare with the reverse
def lcs(a, b): prev = [0] * (len(b) + 1) for x in a: cur = [0] for j, y in enumerate(b, 1): cur.append(prev[j - 1] + 1 if x == y else max(prev[j], cur[j - 1])) prev = cur return prev[-1]
s = "agbcba"print(lcs(s, s[::-1]))5
What this code does
- The longest palindromic subsequence of s equals the longest common subsequence of s and its reverse.
- It reuses a function you already trust. The interval table above is the one to write when you must explain the idea.
The loop runs i downwards because lps[i][j] reads row i + 1, which must already be done. The cost is O(n squared) time and space.
Interval DP with a split point
Interval DP stores an answer for every range i to j of a sequence. A longer range is built from shorter ranges inside it, often by trying every split point, so ranges are filled in order of increasing length.
Some answers for a range need a choice of where to cut it. Multiplying a chain of matrices costs different amounts depending on where you place the brackets. Try every split point k and add the two parts plus the cost of joining them.
def chain_cost(dims): n = len(dims) - 1 cost = [[0] * n for _ in range(n)] for length in range(2, n + 1): for i in range(n - length + 1): j = i + length - 1 cost[i][j] = min( cost[i][k] + cost[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1] for k in range(i, j) ) return cost[0][n - 1] if n else 0Example 6 · Cheapest way to multiply matrices
def chain_cost(dims): n = len(dims) - 1 cost = [[0] * n for _ in range(n)] for length in range(2, n + 1): for i in range(n - length + 1): j = i + length - 1 cost[i][j] = min( cost[i][k] + cost[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1] for k in range(i, j) ) return cost[0][n - 1] if n else 0
print(chain_cost([10, 30, 5, 60]))print(chain_cost([40, 20, 30, 10, 30]))4500 26000
What this code does
- The first chain is 10 x 30, 30 x 5 and 5 x 60. Joining the first two before the last costs 1500 + 3000 = 4500.
- The second chain has four matrices, and trying every split point finds the cheapest bracket placement.
Matrix i has size dims[i] by dims[i + 1]. Joining two parts costs dims[i] x dims[k + 1] x dims[j + 1]. With n matrices the cost is O(n cubed) time and O(n squared) space.
The loop order must respect the dependencies
A cell needs cells for shorter ranges. Loop by length, shortest first, or loop i downwards and j upwards. Looping i upwards reads cells that are not filled yet, and you silently read zeros instead of an error.
# Order 1: by lengthfor length in range(1, n + 1): for i in range(n - length + 1): j = i + length - 1
# Order 2: i from the end, j from ifor i in range(n - 1, -1, -1): for j in range(i, n): passExample 7 · A wrong loop order gives wrong answers
def lps_wrong(s): n = len(s) lps = [[0] * n for _ in range(n)] for i in range(n): lps[i][i] = 1 for j in range(i + 1, n): if s[i] == s[j]: lps[i][j] = lps[i + 1][j - 1] + 2 if i + 1 < n else 2 else: lps[i][j] = max(lps[i + 1][j], lps[i][j - 1]) return lps[0][n - 1]
print(lps_wrong("agbcba"))2
What this code does
- With i going upwards, lps[i + 1][j] has not been computed yet, so it is still 0.
- The code runs without an error and prints a wrong number, 2, instead of 5. That is why the loop order needs care.
Both orders visit every range after the ranges inside it. Pick the one that matches how your rule reads its neighbours.
Next step
Check your understanding
12 quick questions