238. Longest Palindromic Subsequence
🔗 LeetCode Problem: 516. Longest Palindromic Subsequence
📊 Difficulty: Medium
🏷️ Topics: Dynamic Programming, String, DP - Strings
Problem Statement
Given a string s, find the longest palindromic subsequence's length in s.
A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
Example 1:
Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".
Example 2:
Input: s = "cbbd"
Output: 2
Explanation: One possible longest palindromic subsequence is "bb".
Constraints:
- 1 <= s.length <= 1000
- s consists only of lowercase English letters.
🧒 Let's Start from the Very Beginning
First - What's a Subsequence?
Forget the problem for a second. Let's understand "subsequence":
String: "hello"
Subsequences (pick letters in order, can skip):
"h" ✓ (picked h)
"e" ✓ (picked e)
"hlo" ✓ (picked h, l, o - skipped e, l)
"eo" ✓ (picked e, o - skipped h, l, l)
"hello" ✓ (picked all)
"" ✓ (picked none)
NOT subsequences (order changed):
"olle" ✗ (o comes before l? No!)
"leh" ✗ (order is wrong)
KEY RULE: You can SKIP letters, but you can't REARRANGE!
Think of it like highlighting text:
"h e l l o"
✓ ✗ ✓ ✗ ✓ → "hlo" ✓
You highlight from left to right, never go back!
Second - What's a Palindrome?
A palindrome reads the same forwards and backwards:
"racecar" → r a c e c a r
← same both ways →
"aba" → a b a
← same →
"bb" → b b
← same →
Non-palindromes:
"abc" → forwards: abc, backwards: cba ✗
"hello" → forwards: hello, backwards: olleh ✗
So a palindrome is SYMMETRIC! Like a mirror! 🪞
Now - What's a Palindromic Subsequence?
A subsequence that happens to be a palindrome!
Example: s = "bbbab"
All possible subsequences:
"b", "bb", "bbb", "ba", "bab", "bbba", "bbbb", "bbbab", ...
Which are palindromes?
"b" ✓ (single letter)
"bb" ✓ (b b - same forwards/backwards)
"bbb" ✓ (b b b - symmetric)
"bbbb" ✓ (b b b b - symmetric)
"bab" ✓ (b a b - symmetric)
"aba" ✓ (a b a - symmetric)
Which is longest?
"bbbb" has length 4! ✓
That's our answer!
🎨 Let's Play With Examples
Example 1: "bbbab" - Let me find ALL palindromic subsequences
s = "bbbab"
01234 (indices)
Let me systematically find them:
Length 1 (all single letters are palindromes):
"b" (index 0)
"b" (index 1)
"b" (index 2)
"a" (index 3)
"b" (index 4)
All length 1! ✓
Length 2:
Can I make "bb"?
Take s[0]='b' and s[1]='b' → "bb" ✓
Take s[0]='b' and s[2]='b' → "bb" ✓
Take s[1]='b' and s[2]='b' → "bb" ✓
... many ways!
Can I make "aa"?
Only one 'a', so NO ✗
Length 3:
Can I make "bbb"?
Take s[0], s[1], s[2] → "bbb" ✓
Can I make "bab"?
Take s[0]='b', s[3]='a', s[4]='b' → "bab" ✓
Can I make "aba"?
Need: 'a' then 'b' then 'a'
s[3]='a', then... we need 'b' AFTER 'a'
s[4]='b', then... we need 'a' AFTER index 4
No 'a' after index 4! ✗
We CAN'T make "aba" in order! ✗
Length 4:
Can I make "bbbb"?
Take s[0]='b', s[1]='b', s[2]='b', s[4]='b'
(skip s[3]='a')
"bbbb" ✓ This is a palindrome!
Length 5:
Can I make "bbbab" a palindrome?
"bbbab" backwards is "babbb" ✗
Not a palindrome!
LONGEST: "bbbb" with length 4! ✓
Example 2: "cbbd" - Let me trace carefully
s = "cbbd"
0123 (indices)
Length 1:
"c", "b", "b", "d" - all palindromes ✓
Length 2:
"cc"? Only one 'c' ✗
"bb"? Take s[1]='b' and s[2]='b' → "bb" ✓
"dd"? Only one 'd' ✗
Length 3:
"cbc"? Take s[0]='c', s[1]='b'... need another 'c'
But there's no 'c' after 'b'! ✗
"bbb"? Only two b's ✗
Length 4:
Can't form any length-4 palindrome
Looks like longest is "bb" with length 2! ✓
🤔 Discovery - What Patterns Do I Notice?
Observation 1: The First and Last Characters Matter!
Let me think about string s:
s = "b b b a b"
↑ ↑
first last
Both are 'b'! They match! 🎯
If first and last match, they could BOTH be in the palindrome!
Like making a sandwich:
first 'b' | middle stuff | last 'b'
The middle stuff also needs to be a palindrome!
Example: "bbbab"
First='b', Last='b' → they match!
Middle: "bba"
If "bba" has a palindrome of length X,
Then "b(bba)b" has palindrome of length X+2! ✓
Observation 2: What if First and Last DON'T Match?
s = "c b b d"
↑ ↑
first last
First='c', Last='d' → different! ✗
They can't BOTH be in the palindrome!
So we have TWO choices:
Choice 1: Ignore the first 'c', work with "bbd"
Choice 2: Ignore the last 'd', work with "cbb"
Try both! Pick whichever gives longer palindrome!
Example: "cbbd"
Choice 1: "bbd" → longest palindrome "bb" (length 2)
Choice 2: "cbb" → longest palindrome "bb" (length 2)
Both give 2! ✓
Observation 3: This is RECURSIVE!
Let me define a function:
longestPalindrome(left, right):
"Find longest palindromic subsequence in s[left...right]"
Case 1: If s[left] == s[right]
They both can be in palindrome!
Answer = 2 + longestPalindrome(left+1, right-1)
Why +2? Because we include both s[left] and s[right]!
Case 2: If s[left] != s[right]
They can't both be in palindrome!
Try both:
Option 1: Skip left, check s[left+1...right]
Option 2: Skip right, check s[left...right-1]
Answer = max(option1, option2)
Base case: If left > right
Empty string → length 0
Base case: If left == right
Single character → length 1
This is BEAUTIFUL! 🌟
💡 Let's Trace This By Hand!
Example: s = "bbbab"
Let me trace: longestPalindrome(0, 4)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
longestPalindrome(0, 4): // "bbbab"
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
left=0, right=4
s[0]='b', s[4]='b'
They match! ✓
Answer = 2 + longestPalindrome(1, 3)
longestPalindrome(1, 3): // "bba"
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
left=1, right=3
s[1]='b', s[3]='a'
They don't match! ✗
Option 1: Skip left → longestPalindrome(2, 3)
Option 2: Skip right → longestPalindrome(1, 2)
Answer = max(option1, option2)
Let me follow Option 1 first:
longestPalindrome(2, 3): // "ba"
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
left=2, right=3
s[2]='b', s[3]='a'
They don't match! ✗
Option 1: Skip left → longestPalindrome(3, 3)
Option 2: Skip right → longestPalindrome(2, 2)
longestPalindrome(3, 3): // "a"
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
left=3, right=3
Same position! Single character!
Return 1
longestPalindrome(2, 2): // "b"
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
left=2, right=2
Same position! Single character!
Return 1
Back to longestPalindrome(2, 3):
max(1, 1) = 1
Return 1
Now Option 2:
longestPalindrome(1, 2): // "bb"
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
left=1, right=2
s[1]='b', s[2]='b'
They match! ✓
Answer = 2 + longestPalindrome(2, 1)
longestPalindrome(2, 1): // left > right
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
left > right → empty string
Return 0
Back to longestPalindrome(1, 2):
2 + 0 = 2
Return 2
Back to longestPalindrome(1, 3):
max(option1=1, option2=2) = 2
Return 2
Back to longestPalindrome(0, 4):
2 + 2 = 4
Return 4 ✓
ANSWER: 4!
The palindrome we found: "bbbb"
- Outer: s[0]='b' and s[4]='b'
- Inner: s[1]='b' and s[2]='b'
Total: "bbbb"! ✓
🎯 The Pattern Emerges!
Understanding the Recursive Structure
Think of it like peeling an onion:
s = " b b b a b "
↑ ↑
Match! So include both!
Now check inside: " b b a "
↑ ↑
Don't match! Try both:
Skip left: "b a"
Skip right: "b b"
"b b" is better (length 2)!
Put it together:
Outer "b...b" (length 2)
+ Inner "bb" (length 2)
= Total "bbbb" (length 4)! ✓
It's RECURSIVE PEELING! Like a matryoshka doll! 🪆
🔴 Approach 1: Recursion (What We Discovered!)
📝 Implementation
class Solution {
public int longestPalindromeSubseq(String s) {
return helper(s, 0, s.length() - 1);
}
private int helper(String s, int left, int right) {
// Base case: empty string
if (left > right) {
return 0;
}
// Base case: single character
if (left == right) {
return 1;
}
// Case 1: Endpoints match
if (s.charAt(left) == s.charAt(right)) {
return 2 + helper(s, left + 1, right - 1);
}
// Case 2: Endpoints don't match
int option1 = helper(s, left + 1, right); // Skip left
int option2 = helper(s, left, right - 1); // Skip right
return Math.max(option1, option2);
}
}
Why This Is Slow
Time Complexity: O(2^n)
At each step (when endpoints don't match), we try 2 options
Tree branches exponentially!
For n=1000:
2^1000 = way too much! ❌
But notice: We compute same (left, right) many times!
PERFECT for memoization! →
🟡 Approach 2: Memoization (Cache the Results!)
🎯 What Do We Cache?
State: (left, right)
Represents substring s[left...right]
Question: "What's longest palindrome in s[left...right]?"
memo[left][right] = answer for this substring
Once computed, store it!
Next time we see same (left, right) → instant answer! ✓
📝 Implementation
class Solution {
private int[][] memo;
public int longestPalindromeSubseq(String s) {
int n = s.length();
memo = new int[n][n];
// Initialize with -1 (not computed)
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
memo[i][j] = -1;
}
}
return helper(s, 0, n - 1);
}
private int helper(String s, int left, int right) {
if (left > right) return 0;
if (left == right) return 1;
// Check memo
if (memo[left][right] != -1) {
return memo[left][right];
}
int result;
if (s.charAt(left) == s.charAt(right)) {
result = 2 + helper(s, left + 1, right - 1);
} else {
int option1 = helper(s, left + 1, right);
int option2 = helper(s, left, right - 1);
result = Math.max(option1, option2);
}
// Cache result
memo[left][right] = result;
return result;
}
}
📊 Complexity
Time: O(n²) - Each state computed once
Space: O(n²) - Memo table + recursion stack
🟢 Approach 3: Bottom-Up DP - UNIFORM LOOP PATTERN
🎯 Understanding dp[i][j]
dp[i][j] = longest palindromic subsequence in s[i...j]
Example: s = "bbbab"
j→ 0 1 2 3 4
i↓ b b b a b
0 b ? ? ? ? ?
1 b ? ? ? ?
2 b ? ? ?
3 a ? ?
4 b ?
We want dp[0][4] (entire string)!
🧒 Why Can't We Use Standard i,j Loops?
PROBLEM: The dependency pattern!
To compute dp[i][j], we need:
- dp[i+1][j-1] (diagonal below-left)
- dp[i+1][j] (directly below)
- dp[i][j-1] (directly left)
Let me show you with the table:
0 1 2 3 4
0 X ? ? ? ?
1 X ? ? ?
2 X ? ?
3 X ?
4 X
To compute dp[0][1], we need dp[1][0] (below-left)
To compute dp[0][2], we need dp[1][1] (below-left)
So we MUST fill BOTTOM-UP and RIGHT-TO-LEFT!
Standard pattern won't work:
for i = 0 to n:
for j = 0 to n: ✗ This goes left-to-right!
🔑 The Solution: Loop BACKWARDS on i!
CORRECT PATTERN:
for i from n-1 down to 0: // Bottom to top
for j from i to n-1: // Left to right (but only where j >= i)
Why this works:
0 1 2 3 4
0 ← Start here (last row of i loop)
1 ← Second
2 ← Third
3 ← Fourth
4 ← Fifth (first iteration, i=4)
When we process i=4:
We fill diagonal: dp[4][4]
When we process i=3:
We fill: dp[3][3], dp[3][4]
dp[3][4] needs dp[4][3] (already filled? No, but j must be >= i!)
When we process i=2:
We fill: dp[2][2], dp[2][3], dp[2][4]
dp[2][4] needs dp[3][3] (already filled ✓) and dp[2][3] (to the left ✓)
This ensures all dependencies are met! ✓
📝 Implementation with UNIFORM Pattern
class Solution {
public int longestPalindromeSubseq(String s) {
int n = s.length();
// dp[i][j] = longest palindrome in s[i...j]
int[][] dp = new int[n][n];
// UNIFORM LOOP PATTERN
// i goes BACKWARDS (bottom to top)
// j goes FORWARDS (left to right, where j >= i)
for (int i = n - 1; i >= 0; i--) {
dp[i][i] = 1; // Base case: single character
for (int j = i + 1; j < n; j++) {
if (s.charAt(i) == s.charAt(j)) {
// Endpoints match
dp[i][j] = 2 + dp[i + 1][j - 1];
} else {
// Endpoints don't match
dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
return dp[0][n - 1];
}
}
🔍 Understanding the Loop Pattern
WHY i BACKWARDS?
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
To compute dp[i][j], we need dp[i+1][j-1]
dp[i+1] is the ROW BELOW i
We need it to be computed FIRST!
So we start from LAST row (i = n-1) and go UP!
for i from n-1 down to 0: ✓
WHY j from i+1?
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
dp[i][j] represents substring s[i...j]
This only makes sense when j >= i!
When i=j: single character (base case)
When j > i: substring with 2+ characters
So j starts at i+1 (or i for base case)
for j from i+1 to n-1: ✓
WHY j-1 is safe?
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
When we access dp[i][j-1]:
j-1 >= i (because j >= i+1, so j-1 >= i)
This was computed in the SAME iteration (inner loop)!
Safe! ✓
WHY i+1 is safe?
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
When we access dp[i+1][j-1] or dp[i+1][j]:
i+1 is the row below
We already processed i+1 (because i goes backwards)!
Safe! ✓
COMPLETE PATTERN:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
for (int i = n - 1; i >= 0; i--) { // Bottom-up
dp[i][i] = 1; // Base case
for (int j = i + 1; j < n; j++) { // Left-to-right
// Standard DP logic
if (s[i] == s[j]) {
dp[i][j] = 2 + dp[i+1][j-1]; // Both safe!
} else {
dp[i][j] = max(dp[i+1][j], dp[i][j-1]); // Both safe!
}
}
}
This is UNIFORM with other DP problems! ✓
Just i goes BACKWARDS instead of forwards!
🔍 Complete Dry Run: s = "bbbab"
n = 5, s = "bbbab"
Iteration i=4 (last row):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
dp[4][4] = 1 (base case)
j loop: j from 5 to 4 (no iterations)
0 1 2 3 4
0
1
2
3
4 1
Iteration i=3:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
dp[3][3] = 1 (base case)
j=4:
s[3]='a', s[4]='b' → different
dp[3][4] = max(dp[4][4], dp[3][3]) = max(1, 1) = 1
0 1 2 3 4
0
1
2
3 1 1
4 1
Iteration i=2:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
dp[2][2] = 1 (base case)
j=3:
s[2]='b', s[3]='a' → different
dp[2][3] = max(dp[3][3], dp[2][2]) = max(1, 1) = 1
j=4:
s[2]='b', s[4]='b' → match!
dp[2][4] = 2 + dp[3][3] = 2 + 1 = 3
0 1 2 3 4
0
1
2 1 1 3
3 1 1
4 1
Iteration i=1:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
dp[1][1] = 1 (base case)
j=2:
s[1]='b', s[2]='b' → match!
dp[1][2] = 2 + dp[2][1]
But dp[2][1] was never computed (j < i)
When i+1=2, j-1=1, that's dp[2][1]
This means j-1 < i+1, so it's 0!
dp[1][2] = 2 + 0 = 2
j=3:
s[1]='b', s[3]='a' → different
dp[1][3] = max(dp[2][3], dp[1][2]) = max(1, 2) = 2
j=4:
s[1]='b', s[4]='b' → match!
dp[1][4] = 2 + dp[2][3] = 2 + 1 = 3
0 1 2 3 4
0
1 1 2 2 3
2 1 1 3
3 1 1
4 1
Iteration i=0:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
dp[0][0] = 1 (base case)
j=1:
s[0]='b', s[1]='b' → match!
dp[0][1] = 2 + dp[1][0] = 2 + 0 = 2
j=2:
s[0]='b', s[2]='b' → match!
dp[0][2] = 2 + dp[1][1] = 2 + 1 = 3
j=3:
s[0]='b', s[3]='a' → different
dp[0][3] = max(dp[1][3], dp[0][2]) = max(2, 3) = 3
j=4:
s[0]='b', s[4]='b' → match!
dp[0][4] = 2 + dp[1][3] = 2 + 2 = 4 ✓
0 1 2 3 4
0 1 2 3 3 4
1 1 2 2 3
2 1 1 3
3 1 1
4 1
ANSWER: dp[0][4] = 4 ✓
Understanding Why This Pattern Works
VISUAL DEPENDENCY:
0 1 2 3 4
0 ✓ → ← needs these
1 ✓ → ← needs these
2 ✓ → ← needs these
3 ✓ → needs this
4 ✓
To compute dp[0][4]:
Needs dp[1][3] (computed in i=1 iteration)
Needs dp[0][3] (computed in SAME iteration, earlier)
To compute dp[1][3]:
Needs dp[2][2] (computed in i=2 iteration)
Needs dp[1][2] (computed in SAME iteration, earlier)
By going i BACKWARDS and j FORWARDS:
- All i+1 values computed in previous iterations ✓
- All j-1 values computed in current iteration ✓
Perfect! ✓
This is the STANDARD pattern for substring DP! ✓
📊 Complexity
Time: O(n²)
Space: O(n²)
🤔 Deep Dive: Can We Use Forward Loops (i=0 to n-1)?
Short Answer: YES! But we need to think differently!
There are actually TWO valid approaches for bottom-up:
Approach A: Index-based (i backward) Approach B: Length-based (forward!)
Let me show you both!
Approach A: Index-Based (What We Did) - i BACKWARD
Pattern: Process by INDEX position
for (int i = n-1; i >= 0; i--) { // Start from END
for (int j = i; j < n; j++) {
// Process substring s[i...j]
}
}
Why backward?
To compute dp[i][j], we need dp[i+1][...]
i+1 must be computed FIRST
So start from i=n-1 and go down to i=0
This is what we used! ✓
Approach B: Length-Based (FORWARD!) - The Alternative!
Pattern: Process by SUBSTRING LENGTH
for (int len = 1; len <= n; len++) { // Start from length 1
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
// Process substring s[i...j] of length 'len'
}
}
Why this works?
When processing length 'len', we need length 'len-2'
Length 'len-2' was already processed in earlier iteration!
This is ALSO valid! ✓
Let me show both in detail:
📊 Detailed Comparison: Both Approaches
Approach A: Index-Based (i backward, j forward)
ITERATION ORDER:
i=4: Process dp[4][4]
i=3: Process dp[3][3], dp[3][4]
i=2: Process dp[2][2], dp[2][3], dp[2][4]
i=1: Process dp[1][1], dp[1][2], dp[1][3], dp[1][4]
i=0: Process dp[0][0], dp[0][1], dp[0][2], dp[0][3], dp[0][4]
Visual:
0 1 2 3 4
0 5 10 15 20 25 ← Last (i=0)
1 4 9 14 19 ← 4th (i=1)
2 3 8 13 ← 3rd (i=2)
3 2 7 ← 2nd (i=3)
4 1 ← First (i=4)
Code:
for (int i = n-1; i >= 0; i--) {
dp[i][i] = 1;
for (int j = i+1; j < n; j++) {
if (s.charAt(i) == s.charAt(j)) {
dp[i][j] = 2 + dp[i+1][j-1];
} else {
dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
}
}
}
Approach B: Length-Based (len forward, i forward)
ITERATION ORDER:
len=1: Process all length-1 substrings
dp[0][0], dp[1][1], dp[2][2], dp[3][3], dp[4][4]
len=2: Process all length-2 substrings
dp[0][1], dp[1][2], dp[2][3], dp[3][4]
len=3: Process all length-3 substrings
dp[0][2], dp[1][3], dp[2][4]
len=4: Process all length-4 substrings
dp[0][3], dp[1][4]
len=5: Process all length-5 substrings
dp[0][4]
Visual:
0 1 2 3 4
0 1 2 3 4 5 ← len increases →
1 1 2 3 4
2 1 2 3
3 1 2
4 1
Code:
for (int len = 1; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
if (len == 1) {
dp[i][j] = 1;
} else if (s.charAt(i) == s.charAt(j)) {
if (len == 2) {
dp[i][j] = 2;
} else {
dp[i][j] = 2 + dp[i+1][j-1];
}
} else {
dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
}
}
}
🎯 Why BOTH Work - The Key Insight!
The secret: DEPENDENCY SATISFACTION
Approach A (Index-based):
When at i, we need i+1
By going BACKWARD (i--), we ensure i+1 is computed first
Dependencies: ROW-based
Approach B (Length-based):
When at len, we need len-2
By going FORWARD (len++), we ensure len-2 is computed first
Dependencies: LENGTH-based
BOTH satisfy dependencies, just in different order! ✓
Visual Proof - Length-Based Works!
s = "bbbab", n = 5
len=1 iteration:
Fill: dp[0][0]=1, dp[1][1]=1, dp[2][2]=1, dp[3][3]=1, dp[4][4]=1
No dependencies! ✓
len=2 iteration:
Fill: dp[0][1], dp[1][2], dp[2][3], dp[3][4]
For dp[0][1]:
Need: dp[1][0] (when i+1=1, j-1=0)
But j-1 < i+1, so this is empty string = 0 ✓
For dp[1][2]:
Need: dp[2][1]
But j-1 < i+1, so this is 0 ✓
All dependencies met! ✓
len=3 iteration:
Fill: dp[0][2], dp[1][3], dp[2][4]
For dp[0][2]:
Need: dp[1][1] (already computed in len=1!) ✓
For dp[2][4]:
Need: dp[3][3] (already computed in len=1!) ✓
All dependencies met! ✓
len=4 iteration:
For dp[0][3]:
Need: dp[1][2] (already computed in len=2!) ✓
For dp[1][4]:
Need: dp[2][3] (already computed in len=2!) ✓
len=5 iteration:
For dp[0][4]:
Need: dp[1][3] (already computed in len=3!) ✓
Everything works! ✓
📊 When to Use Which Approach?
┌─────────────────────────────────────────────────────┐
│ INDEX-BASED vs LENGTH-BASED │
├─────────────────────────────────────────────────────┤
│ │
│ INDEX-BASED (i backward): │
│ ✓ More intuitive (matches recursion) │
│ ✓ Standard for most DP problems │
│ ✓ Easier to understand dependencies │
│ Use: General substring DP │
│ │
│ LENGTH-BASED (len forward): │
│ ✓ Natural forward iteration │
│ ✓ Good when thinking "small to large" │
│ ✓ Clear progression (len 1→2→3...) │
│ Use: Interval DP, when length matters │
│ │
│ BOTH ARE EQUALLY VALID! ✓ │
│ │
└─────────────────────────────────────────────────────┘
Personal preference:
I prefer INDEX-BASED because it's more standard
and matches other DP problems better.
But LENGTH-BASED is completely correct too!
🤔 So Why Did I Use Index-Based?
REASON 1: Consistency
Most DP problems use index-based iteration
LCS, Edit Distance, Knapsack all use i,j directly
REASON 2: Pattern Recognition
When you see dp[i][j] needing dp[i+1][...]:
→ Think "i goes backward"
This pattern works across MANY problems!
REASON 3: Simplicity
Length-based needs:
- Extra variable (len)
- Calculate j from i and len
- More edge cases (len==1, len==2)
Index-based is cleaner:
- Just i and j
- Direct access
- Fewer special cases
BUT: Length-based is NOT wrong!
It's a valid alternative! ✓
🎯 The REAL Answer to Your Question
Question: "Why can't we use forward loops i=0 to n-1?"
Answer: We CAN! Two ways:
METHOD 1 (What you were thinking):
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
// This WON'T work ✗
}
}
Problem: At i=0, need i=1 which isn't computed yet
METHOD 2 (Length-based - WORKS!):
for (int len = 1; len <= n; len++) {
for (int i = 0; i <= n-len; i++) {
int j = i + len - 1;
// This WORKS! ✓
}
}
Why: At len=3, need len=1 which was computed earlier!
So the answer is:
- Direct i forward doesn't work ✗
- But len forward DOES work! ✓
- i backward also works! ✓
Pick whichever you find clearer! ✓
💡 Final Recommendation
MY SUGGESTION: Learn BOTH patterns!
INDEX-BASED (i backward):
Use this as your DEFAULT
It's more standard and transferable
LENGTH-BASED (len forward):
Know it exists!
Some problems are clearer with this
Valid alternative!
In interviews:
Either approach is correct!
Use whichever you're comfortable with!
The important part:
Understand WHY it works! ✓
Understanding the Dependency Direction
Let me visualize what dp[i][j] NEEDS:
When computing dp[i][j]:
If s[i] == s[j]:
Needs: dp[i+1][j-1] (diagonal below-left)
Else:
Needs: dp[i+1][j] (directly below)
Needs: dp[i][j-1] (directly left)
Visual:
j-1 j
i ? [i,j] ← We're computing this
↑
i+1 ? ? ← We NEED these!
↑
Arrow points DOWN and LEFT!
We need values BELOW and to the LEFT!
If we go FORWARD (i=0,1,2...):
When at i=0, we need i=1 (not computed yet!) ❌
If we go BACKWARD (i=n-1,n-2,...,0):
When at i=0, we already computed i=1! ✓
DIRECTION MATTERS! 🔑
The Complete Picture with Arrows
s = "bbbab", n = 5
0 1 2 3 4
0 1 →[?]→[?]→[?]→[?]
↗ ↗ ↗ ↗
1 1 →[?]→[?]→[?]
↗ ↗ ↗
2 1 →[?]→[?]
↗ ↗
3 1 →[?]
↗
4 1
Arrows show dependency direction:
→ means "needs value to the left"
↗ means "needs value diagonally below-left"
To fill dp[0][1]:
Need dp[1][0] (diagonal ↗)
To fill dp[0][2]:
Need dp[1][1] (diagonal ↗)
Need dp[0][1] (left →)
MUST fill from BOTTOM-UP! ✓
Why Backwards Works
BACKWARD ITERATION (i = n-1 down to 0):
Iteration i=4 (bottom row):
Fill: dp[4][4] = 1
No dependencies! ✓
Iteration i=3:
Fill: dp[3][3] = 1
Fill: dp[3][4]
Needs: dp[4][3] (not needed, j-1 < i)
Needs: dp[3][3] (already filled in SAME iteration) ✓
Needs: dp[4][4] (already filled in PREVIOUS iteration) ✓
All dependencies met! ✓
Iteration i=2:
Fill: dp[2][2], dp[2][3], dp[2][4]
For dp[2][4]:
Needs: dp[3][3] (filled in previous iteration) ✓
Needs: dp[2][3] (filled earlier in SAME iteration) ✓
All dependencies met! ✓
...and so on!
By going BACKWARDS on i and FORWARDS on j:
- i+1 rows already filled (previous iterations) ✓
- j-1 columns already filled (current iteration) ✓
Perfect! ✓
🎯 When Can We Use Forward Loops?
Pattern 1: Dependencies Go RIGHT and DOWN
Example: Longest Common Subsequence
dp[i][j] needs:
- dp[i-1][j-1] (diagonal above-left)
- dp[i-1][j] (directly above)
- dp[i][j-1] (directly left)
Visual:
i-1 ? ? ← We NEED these!
↑ ↑
i ? [i,j] ← We're computing this
↑
Arrows point UP and LEFT!
Can use FORWARD loops:
for (int i = 0; i < n; i++) { // Forward ✓
for (int j = 0; j < m; j++) { // Forward ✓
// i-1 already computed (previous iteration)
// j-1 already computed (current iteration)
}
}
This works! ✓
Pattern 2: Dependencies Go ONLY RIGHT
Example: House Robber (1D DP)
dp[i] needs:
- dp[i-1]
- dp[i-2]
These are ALL to the LEFT!
Can use FORWARD loop:
for (int i = 0; i < n; i++) { // Forward ✓
// i-1, i-2 already computed
}
This works! ✓
Pattern 3: Dependencies Go DOWN and LEFT (OUR CASE)
Example: Longest Palindromic Subsequence
dp[i][j] needs:
- dp[i+1][j-1] (diagonal below-left)
- dp[i+1][j] (directly below)
- dp[i][j-1] (directly left)
Visual:
i ? [i,j] ← We're computing this
↓ ↓
i+1 ? ? ← We NEED these!
Arrows point DOWN and LEFT!
CANNOT use forward on i:
for (int i = 0; i < n; i++) { // Forward ✗
// i+1 NOT computed yet! ❌
}
MUST use backward on i:
for (int i = n-1; i >= 0; i--) { // Backward ✓
for (int j = i; j < n; j++) { // Forward ✓
// i+1 already computed (previous iteration)
// j-1 already computed (current iteration)
}
}
This works! ✓
📊 Summary: Loop Direction Rules
DEPENDENCY DIRECTION → LOOP DIRECTION
If dependencies point UP/LEFT:
→ Use FORWARD loops (i++, j++)
→ Example: LCS, Edit Distance, Knapsack
If dependencies point DOWN/LEFT:
→ Use BACKWARD i loop (i--)
→ Use FORWARD j loop (j++)
→ Example: Palindromic Subsequence, Interval DP
If dependencies point RIGHT:
→ Use FORWARD loop (i++)
→ Example: 1D DP, Fibonacci
RULE OF THUMB:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Look at your recurrence relation!
If you access dp[i+1][...]: → i goes BACKWARD
If you access dp[i-1][...]: → i goes FORWARD
If you access dp[...][j+1]: → j goes BACKWARD
If you access dp[...][j-1]: → j goes FORWARD
Match the loop to the dependency! 🔑
Visual Reference
┌─────────────────────────────────────────────────────┐
│ DEPENDENCY vs LOOP DIRECTION │
├─────────────────────────────────────────────────────┤
│ │
│ Dependencies → UP/LEFT │
│ i-1, j-1 │
│ Loop: i FORWARD, j FORWARD │
│ Example: LCS │
│ │
│ Dependencies → DOWN/LEFT │
│ i+1, j-1 │
│ Loop: i BACKWARD, j FORWARD │
│ Example: Palindromic Subsequence │
│ │
│ Dependencies → ONLY LEFT │
│ i-1, i-2 │
│ Loop: i FORWARD │
│ Example: House Robber │
│ │
└─────────────────────────────────────────────────────┘
GOLDEN RULE:
You must compute dependencies BEFORE you need them!
Design your loop to ensure this! ✓
💻 Complete Working Code
class Solution {
public int longestPalindromeSubseq(String s) {
return bottomUpDP(s);
}
// Approach 3A: Bottom-Up DP (Index-based) - O(n²)
private int bottomUpDP(String s) {
int n = s.length();
int[][] dp = new int[n][n];
// INDEX-BASED: i backwards, j forwards
for (int i = n - 1; i >= 0; i--) {
dp[i][i] = 1; // Base case
for (int j = i + 1; j < n; j++) {
if (s.charAt(i) == s.charAt(j)) {
dp[i][j] = 2 + (i + 1 <= j - 1 ? dp[i + 1][j - 1] : 0);
} else {
dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
return dp[0][n - 1];
}
// Approach 3B: Bottom-Up DP (Length-based) - O(n²)
private int bottomUpDPLengthBased(String s) {
int n = s.length();
int[][] dp = new int[n][n];
// LENGTH-BASED: len forwards, i forwards
for (int len = 1; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
if (len == 1) {
dp[i][j] = 1; // Base case
} else if (s.charAt(i) == s.charAt(j)) {
if (len == 2) {
dp[i][j] = 2;
} else {
dp[i][j] = 2 + dp[i + 1][j - 1];
}
} else {
dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
return dp[0][n - 1];
}
// Approach 2: Memoization - O(n²)
private int[][] memo;
private int memoization(String s) {
int n = s.length();
memo = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
memo[i][j] = -1;
}
}
return helperMemo(s, 0, n - 1);
}
private int helperMemo(String s, int left, int right) {
if (left > right)
return 0;
if (left == right)
return 1;
if (memo[left][right] != -1) {
return memo[left][right];
}
int result;
if (s.charAt(left) == s.charAt(right)) {
result = 2 + helperMemo(s, left + 1, right - 1);
} else {
int option1 = helperMemo(s, left + 1, right);
int option2 = helperMemo(s, left, right - 1);
result = Math.max(option1, option2);
}
memo[left][right] = result;
return result;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.longestPalindromeSubseq("bbbab") == 4);
System.out.println(s.longestPalindromeSubseq("cbbd") == 2);
System.out.println(s.longestPalindromeSubseq("a") == 1);
}
}
🔑 Key Insights
The Uniform Loop Pattern
STANDARD SUBSTRING DP PATTERN:
for (int i = n - 1; i >= 0; i--) { // Backwards
for (int j = i; j < n; j++) { // Forwards
// DP logic using dp[i+1][...] and dp[...][j-1]
}
}
Why backwards?
We need dp[i+1] to compute dp[i]
So process larger i values first!
This pattern appears in:
- Longest Palindromic Subsequence (this problem)
- Longest Palindromic Substring
- Palindrome Partitioning II
- Many interval DP problems
MEMORIZE THIS PATTERN! 🔑
🎪 Memory Aid
"Peel the onion!"
"Endpoints match? Use both!"
"Endpoints differ? Skip one!"
"Loop i BACKWARDS, j forwards!" ✨
📝 Quick Revision
🎯 Core Concept
Problem: Find longest palindromic subsequence
State: dp[i][j] = longest in s[i...j]
Pattern: Substring DP with backwards i loop
⚡ The Uniform Loop
public class Solution {
public int longestPalindromeSubseq(String s) {
// return recurisve(s, 0, s.length() - 1);
// Integer[][] memo = new Integer[s.length()][s.length()];
// return topDown(s, 0, s.length() - 1, memo);
return bottomUp(s);
}
private int bottomUp(String s) {
int len = s.length();
// dp[i][j] => length of the longest palindromic subsequence in substring s[i…j]
int[][] dp = new int[len][len];
// Example: "cbbd"
// i = 3 → dp[3][3]
// i = 2 → dp[2][2], dp[2][3]
// i = 1 → dp[1][1], dp[1][2], dp[1][3]
// i = 0 → dp[0][0], dp[0][1], dp[0][2], dp[0][3]
// Why loop directions are different compared to other problems?
// Here, its a palindorme check.
// Like 2 pointers moving close to each other and so one loop goes up and other goes down.
for (int i = len - 1; i >= 0; i--) {
// base case
// Any single character is a palindrome of length 1
// This initializes the diagonal of the DP table
dp[i][i] = 1;
for (int j = i + 1; j < len; j++) {
if (s.charAt(i) == s.charAt(j)) {
// What does it mean?
// If curr chars at i and j match, shrink left and right both sides
dp[i][j] = 2 + dp[i + 1][j - 1];
} else {
// If curr chars at i and j do not match
// option 1: shrink at right (i, j-1)
// option 2: shrink at left (i+1, j)
// And then find max of both.
dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
}
}
}
// represents the LPS for the full string
return dp[0][len - 1];
}
private int topDown(String s, int left, int right, Integer[][] memo) {
if (left == right) {
return 1;
}
if (left > right) {
return 0;
}
if (memo[left][right] != null) {
return memo[left][right];
}
if (s.charAt(left) == s.charAt(right)) {
return 2 + topDown(s, left + 1, right - 1, memo);
}
int option1 = topDown(s, left, right - 1, memo);
int option2 = topDown(s, left + 1, right, memo);
return memo[left][right] = Math.max(option1, option2);
}
private int recurisve(String s, int left, int right) {
// step 4: base case 1
if (left == right) {
return 1; // considering the left over character
}
// step 5: base case 2
if (left > right) {
return 0;
}
// step 1: chars at indices left and right match
// include in the length and proceed to next character matches.
if (s.charAt(left) == s.charAt(right)) {
return 2 + recurisve(s, left + 1, right - 1);
}
// step 2: skip one time character at unmatching
// right index and consider rest of the substring
int option1 = recurisve(s, left, right - 1);
// step 3: same here. Skip left index char and consider rest.
int option2 = recurisve(s, left + 1, right);
return Math.max(option1, option2);
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.longestPalindromeSubseq("bbbab") == 4);
System.out.println(s.longestPalindromeSubseq("cbbd") == 2);
}
}
Complexity: O(n²) time and space
🎉 Congratulations!
Now you have: - ✅ Intuitive understanding from scratch - ✅ Complete recursive discovery - ✅ Natural memoization - ✅ UNIFORM bottom-up pattern that matches other DP problems!
The loop pattern is now consistent! 🚀✨