Interval DP is a pattern where dp[i][j] represents the answer for the substring or subarray from index i to j. We build up from small intervals to large ones.
In simple language, we start by solving tiny substrings (length 1, length 2), then use those answers to solve bigger and bigger substrings. Think of it like building a pyramid from the bottom up.
These are interview favorites, especially the palindrome family.
Longest Palindromic Subsequence
Problem: Find the length of the longest subsequence that reads the same forwards and backwards. We can skip characters (it’s a subsequence, not a substring).
Example: "bbbab" has LPS "bbbb" (length 4).
State: dp[i][j] = length of longest palindromic subsequence in s[i..j]
Recurrence:
- If
s[i] == s[j]:dp[i][j] = dp[i+1][j-1] + 2(both ends match, shrink inward) - Else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])(try dropping one end)
Base case: Every single character is a palindrome of length 1.
function longestPalindromeSubseq(s) {
const n = s.length;
const dp = Array.from({ length: n }, () => new Array(n).fill(0));
for (let i = 0; i < n; i++) dp[i][i] = 1; // single char = palindrome
for (let len = 2; len <= n; len++) { // grow the interval
for (let i = 0; i <= n - len; i++) {
const j = i + len - 1;
if (s[i] === s[j]) {
dp[i][j] = dp[i + 1][j - 1] + 2; // both ends match
} else {
dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]); // skip one
}
}
}
return dp[0][n - 1];
}
// Time: O(n²), Space: O(n²)def longest_palindrome_subseq(s):
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n):
dp[i][i] = 1 # single char = palindrome
for length in range(2, n + 1): # grow the interval
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j]:
dp[i][j] = dp[i + 1][j - 1] + 2 # both ends match
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) # skip one
return dp[0][n - 1]
# Time: O(n²), Space: O(n²)static int longestPalindromeSubseq(String s) {
int n = s.length();
int[][] dp = new int[n][n];
for (int i = 0; i < n; i++) dp[i][i] = 1;
for (int len = 2; len <= n; len++) { // grow the interval
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
if (s.charAt(i) == s.charAt(j)) {
dp[i][j] = dp[i + 1][j - 1] + 2;
} else {
dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
return dp[0][n - 1];
}
// Time: O(n²), Space: O(n²)Fun fact: LPS is equivalent to finding the LCS of s and reverse(s). Two ways to solve the same problem.
Longest Palindromic Substring
Problem: Find the longest substring (contiguous!) that’s a palindrome.
This one is slightly different from the subsequence version. Instead of tracking length, we track whether s[i..j] is a palindrome.
State: dp[i][j] = true if s[i..j] is a palindrome
Recurrence: dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]
function longestPalindrome(s) {
const n = s.length;
const dp = Array.from({ length: n }, () => new Array(n).fill(false));
let start = 0, maxLen = 1;
for (let i = 0; i < n; i++) dp[i][i] = true; // single chars
for (let len = 2; len <= n; len++) {
for (let i = 0; i <= n - len; i++) {
const j = i + len - 1;
if (s[i] === s[j] && (len <= 3 || dp[i + 1][j - 1])) {
dp[i][j] = true;
if (len > maxLen) { start = i; maxLen = len; }
}
}
}
return s.slice(start, start + maxLen);
}def longest_palindrome(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 # single chars
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j] and (length <= 3 or dp[i + 1][j - 1]):
dp[i][j] = True
if length > max_len:
start, max_len = i, length
return s[start:start + max_len]static String longestPalindrome(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
int start = 0, maxLen = 1;
for (int i = 0; i < n; i++) dp[i][i] = true;
for (int len = 2; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
if (s.charAt(i) == s.charAt(j) && (len <= 3 || dp[i+1][j-1])) {
dp[i][j] = true;
if (len > maxLen) { start = i; maxLen = len; }
}
}
}
return s.substring(start, start + maxLen);
}Note: There’s also a clever expand-around-center approach that uses O(1) space. But the DP version is what demonstrates the interval pattern.
Palindrome Partitioning II (Minimum Cuts)
Problem: Given a string, find the minimum number of cuts to split it so that every piece is a palindrome.
Example: "aab" needs 1 cut: "aa" | "b".
We need two things:
- A palindrome lookup table (is
s[i..j]a palindrome?) - A 1D DP for minimum cuts
State: dp[i] = minimum cuts for s[0..i]
function minCut(s) {
const n = s.length;
// Step 1: precompute palindrome table
const isPalin = Array.from({ length: n }, () => new Array(n).fill(false));
for (let i = n - 1; i >= 0; i--) {
for (let j = i; j < n; j++) {
isPalin[i][j] = s[i] === s[j] && (j - i <= 2 || isPalin[i+1][j-1]);
}
}
// Step 2: find min cuts
const dp = new Array(n).fill(0);
for (let i = 0; i < n; i++) {
if (isPalin[0][i]) { dp[i] = 0; continue; } // whole prefix is palindrome
dp[i] = Infinity;
for (let j = 1; j <= i; j++) {
if (isPalin[j][i]) dp[i] = Math.min(dp[i], dp[j - 1] + 1);
}
}
return dp[n - 1];
}def min_cut(s):
n = len(s)
# Step 1: precompute palindrome table
is_palin = [[False] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
for j in range(i, n):
is_palin[i][j] = s[i] == s[j] and (j - i <= 2 or is_palin[i+1][j-1])
# Step 2: find min cuts
dp = [0] * n
for i in range(n):
if is_palin[0][i]:
dp[i] = 0; continue # whole prefix is palindrome
dp[i] = float('inf')
for j in range(1, i + 1):
if is_palin[j][i]:
dp[i] = min(dp[i], dp[j - 1] + 1)
return dp[n - 1]static int minCut(String s) {
int n = s.length();
boolean[][] isPalin = new boolean[n][n];
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
isPalin[i][j] = s.charAt(i) == s.charAt(j)
&& (j - i <= 2 || isPalin[i+1][j-1]);
}
}
int[] dp = new int[n];
for (int i = 0; i < n; i++) {
if (isPalin[0][i]) { dp[i] = 0; continue; }
dp[i] = Integer.MAX_VALUE;
for (int j = 1; j <= i; j++) {
if (isPalin[j][i]) dp[i] = Math.min(dp[i], dp[j - 1] + 1);
}
}
return dp[n - 1];
}Decode Ways
Problem: A message encoded with ‘A’=1, ‘B’=2, …, ‘Z’=26. Given a digit string, how many ways can we decode it?
Example: "226" can be decoded as “BZ” (2,26), “VF” (22,6), or “BBF” (2,2,6) = 3 ways.
This is actually more of a 1D DP problem, but it involves string parsing with choices, which is why it fits here.
State: dp[i] = number of ways to decode s[0..i-1]
function numDecodings(s) {
if (s[0] === '0') return 0;
const n = s.length;
const dp = new Array(n + 1).fill(0);
dp[0] = 1; // empty string = 1 way
dp[1] = 1; // first char (not '0')
for (let i = 2; i <= n; i++) {
const oneDigit = parseInt(s[i - 1]); // take last 1 digit
const twoDigit = parseInt(s.slice(i - 2, i)); // take last 2 digits
if (oneDigit >= 1) dp[i] += dp[i - 1];
if (twoDigit >= 10 && twoDigit <= 26) dp[i] += dp[i - 2];
}
return dp[n];
}def num_decodings(s):
if s[0] == '0': return 0
n = len(s)
dp = [0] * (n + 1)
dp[0] = 1 # empty string = 1 way
dp[1] = 1 # first char (not '0')
for i in range(2, n + 1):
one_digit = int(s[i - 1]) # take last 1 digit
two_digit = int(s[i - 2:i]) # take last 2 digits
if one_digit >= 1: dp[i] += dp[i - 1]
if 10 <= two_digit <= 26: dp[i] += dp[i - 2]
return dp[n]static int numDecodings(String s) {
if (s.charAt(0) == '0') return 0;
int n = s.length();
int[] dp = new int[n + 1];
dp[0] = 1; dp[1] = 1;
for (int i = 2; i <= n; i++) {
int oneDigit = s.charAt(i - 1) - '0';
int twoDigit = Integer.parseInt(s.substring(i - 2, i));
if (oneDigit >= 1) dp[i] += dp[i - 1];
if (twoDigit >= 10 && twoDigit <= 26) dp[i] += dp[i - 2];
}
return dp[n];
}The Interval DP Pattern
Here’s the template that works for most interval problems:
for length from 2 to n: // interval size
for i from 0 to n-length: // start index
j = i + length - 1 // end index
dp[i][j] = combine(dp[i+1][j], dp[i][j-1], dp[i+1][j-1])The key insight: we process intervals by increasing length. When we compute dp[i][j], all smaller intervals are already filled in.
Common interview problems in this family:
- Longest palindromic subsequence/substring
- Palindrome partitioning
- Burst balloons
- Matrix chain multiplication
- Stone game