Longest Palindromic Subsequence

▶

Steps

setup

Initialize dp array with 1s

We create a dp array of length 5 (string length) and initialize all values to 1, since every single character is a palindrome of length 1.

💡 This initialization sets the base case: each character alone forms a palindrome of length 1.

Line:

dp = [1]*n

💡 Every single character substring is a palindrome of length 1.

fill_row

Start outer loop with i = 3

Set i = 3 (second last index). We will update dp for substrings starting at index 3.

💡 We process substrings from right to left, starting with smaller substrings.

Line:

for i in range(n-2, -1, -1):
    prev = 0

💡 Outer loop controls the start index of substrings considered.

fill_cells

Inner loop j=4, compare s[3] and s[4]

Compare characters s[3] = 'a' and s[4] = 'b'. They do not match, so dp[4] is updated to max(dp[4], dp[3]) = max(1,1) = 1.

💡 When characters differ, we take the best palindrome length from either excluding one end.

Line:

temp = dp[j]
if s[i] == s[j]:
    dp[j] = 2 + prev
else:
    dp[j] = max(dp[j], dp[j-1])
prev = temp

💡 Mismatch means palindrome length doesn't increase here.

fill_row

Decrement i to 2, reset prev

Set i = 2 and reset prev = 0 to start processing substrings starting at index 2.

💡 Resetting prev is necessary to track dp[i+1][j-1] for the new row.

Line:

for i in range(n-2, -1, -1):
    prev = 0

💡 Outer loop moves leftwards, preparing for next substring start.

fill_cells

Inner loop j=3, compare s[2] and s[3]

Compare s[2] = 'b' and s[3] = 'a'. They differ, so dp[3] = max(dp[3], dp[2]) = max(1,1) = 1.

💡 Mismatch means no palindrome extension; take max of excluding one end.

Line:

temp = dp[j]
if s[i] == s[j]:
    dp[j] = 2 + prev
else:
    dp[j] = max(dp[j], dp[j-1])
prev = temp

💡 Mismatch keeps palindrome length unchanged here.

fill_cells

Inner loop j=4, compare s[2] and s[4]

Compare s[2] = 'b' and s[4] = 'b'. They match, so dp[4] = 2 + prev = 2 + 1 = 3.

💡 Matching characters extend palindrome by adding 2 plus dp[i+1][j-1].

Line:

temp = dp[j]
if s[i] == s[j]:
    dp[j] = 2 + prev
else:
    dp[j] = max(dp[j], dp[j-1])
prev = temp

💡 Match extends palindrome length by 2 plus inner substring palindrome.

fill_row

Decrement i to 1, reset prev

Set i = 1 and reset prev = 0 to process substrings starting at index 1.

💡 Moving leftwards to consider longer substrings starting earlier.

Line:

for i in range(n-2, -1, -1):
    prev = 0

💡 Outer loop continues to expand substring start index.

fill_cells

Inner loop j=2, compare s[1] and s[2]

Compare s[1] = 'b' and s[2] = 'b'. They match, so dp[2] = 2 + prev = 2 + 0 = 2.

💡 Match extends palindrome length by 2 plus dp[i+1][j-1].

Line:

temp = dp[j]
if s[i] == s[j]:
    dp[j] = 2 + prev
else:
    dp[j] = max(dp[j], dp[j-1])
prev = temp

💡 Palindrome length increases for substring s[1..2].

fill_cells

Inner loop j=3, compare s[1] and s[3]

Compare s[1] = 'b' and s[3] = 'a'. They differ, so dp[3] = max(dp[3], dp[2]) = max(1, 2) = 2.

💡 Mismatch means take the best palindrome length from excluding one end.

Line:

temp = dp[j]
if s[i] == s[j]:
    dp[j] = 2 + prev
else:
    dp[j] = max(dp[j], dp[j-1])
prev = temp

💡 Palindrome length updated to best known for substring s[1..3].

fill_cells

Inner loop j=4, compare s[1] and s[4]

Compare s[1] = 'b' and s[4] = 'b'. They match, so dp[4] = 2 + prev = 2 + 1 = 3.

💡 Match extends palindrome length by 2 plus dp[i+1][j-1].

Line:

temp = dp[j]
if s[i] == s[j]:
    dp[j] = 2 + prev
else:
    dp[j] = max(dp[j], dp[j-1])
prev = temp

💡 Palindrome length increases for substring s[1..4].

fill_row

Decrement i to 0, reset prev

Set i = 0 and reset prev = 0 to process substrings starting at index 0.

💡 Final outer loop iteration to consider the entire string.

Line:

for i in range(n-2, -1, -1):
    prev = 0

💡 Preparing to update dp for substrings starting at the first character.

fill_cells

Inner loop j=1, compare s[0] and s[1]

Compare s[0] = 'b' and s[1] = 'b'. They match, so dp[1] = 2 + prev = 2 + 0 = 2.

💡 Match extends palindrome length by 2 plus dp[i+1][j-1].

Line:

temp = dp[j]
if s[i] == s[j]:
    dp[j] = 2 + prev
else:
    dp[j] = max(dp[j], dp[j-1])
prev = temp

💡 Palindrome length increases for substring s[0..1].

fill_cells

Inner loop j=2, compare s[0] and s[2]

Compare s[0] = 'b' and s[2] = 'b'. They match, so dp[2] = 2 + prev = 2 + 1 = 3.

💡 Match extends palindrome length by 2 plus dp[i+1][j-1].

Line:

temp = dp[j]
if s[i] == s[j]:
    dp[j] = 2 + prev
else:
    dp[j] = max(dp[j], dp[j-1])
prev = temp

💡 Palindrome length increases for substring s[0..2].

fill_cells

Inner loop j=3, compare s[0] and s[3]

Compare s[0] = 'b' and s[3] = 'a'. They differ, so dp[3] = max(dp[3], dp[2]) = max(2, 3) = 3.

💡 Mismatch means take the best palindrome length from excluding one end.

Line:

temp = dp[j]
if s[i] == s[j]:
    dp[j] = 2 + prev
else:
    dp[j] = max(dp[j], dp[j-1])
prev = temp

💡 Palindrome length updated to best known for substring s[0..3].

fill_cells

Inner loop j=4, compare s[0] and s[4]

Compare s[0] = 'b' and s[4] = 'b'. They match, so dp[4] = 2 + prev = 2 + 2 = 4.

💡 Match extends palindrome length by 2 plus dp[i+1][j-1].

Line:

temp = dp[j]
if s[i] == s[j]:
    dp[j] = 2 + prev
else:
    dp[j] = max(dp[j], dp[j-1])
prev = temp

💡 Longest palindrome length found for entire string s[0..4].

reconstruct

Return final answer dp[n-1]

Return dp[4] = 4 as the length of the longest palindromic subsequence for 'bbbab'.

💡 The last dp element holds the answer for the entire string.

Line:

return dp[n-1]

💡 The algorithm successfully computed the longest palindromic subsequence length.

def longest_palindromic_subsequence(s):
    n = len(s)
    dp = [1]*n  # STEP 1: Initialize dp array
    for i in range(n-2, -1, -1):  # STEP 2,4,7,11: Outer loop over i
        prev = 0  # Reset prev for each i
        for j in range(i+1, n):  # Inner loop over j
            temp = dp[j]  # Store current dp[j]
            if s[i] == s[j]:  # Check characters match
                dp[j] = 2 + prev  # STEP 6,8,10,12,13,15: Update dp[j] on match
            else:
                dp[j] = max(dp[j], dp[j-1])  # STEP 3,5,9,14: Update dp[j] on mismatch
            prev = temp  # Update prev for next iteration
    return dp[n-1]  # STEP 16: Return final answer

if __name__ == '__main__':
    print(longest_palindromic_subsequence('bbbab'))

📊

Longest Palindromic Subsequence - Watch the Algorithm Execute, Step by Step

Watching each update helps you understand how overlapping subproblems are solved and how the algorithm builds up the solution from smaller substrings to the entire string.

Item 0 - wt:0 val:0

i\w	0	1	2	3	4
i=0	1	1	1	1	1

dp[0] = 1

Item 3 - wt:0 val:0

i\w	0	1	2	3	4
i=0	1	1	1	1	1

dp array before updates

Item 3 - wt:0 val:0

i\w	0	1	2	3	4
i=0	1	1	1	1	1

Updating dp[4]

Item 2 - wt:0 val:0

i\w	0	1	2	3	4
i=0	1	1	1	1	1

dp array before updates

Item 2 - wt:0 val:0

i\w	0	1	2	3	4
i=0	1	1	1	1	1

Updating dp[3]

Item 2 - wt:0 val:0

i\w	0	1	2	3	4
i=0	1	1	1	1	3

Updating dp[4] with match

Item 1 - wt:0 val:0

i\w	0	1	2	3	4
i=0	1	1	1	1	3

dp array before updates

Item 1 - wt:0 val:0

i\w	0	1	2	3	4
i=0	1	1	2	1	3

Updating dp[2] with match

Item 1 - wt:0 val:0

i\w	0	1	2	3	4
i=0	1	1	2	2	3

Updating dp[3] with max

Item 1 - wt:0 val:0

i\w	0	1	2	3	4
i=0	1	1	2	2	3

Updating dp[4] with match

Item 0 - wt:0 val:0

i\w	0	1	2	3	4
i=0	1	1	2	2	3

dp array before updates

Item 0 - wt:0 val:0

i\w	0	1	2	3	4
i=0	1	2	2	2	3

Updating dp[1] with match

Item 0 - wt:0 val:0

i\w	0	1	2	3	4
i=0	1	2	3	2	3

Updating dp[2] with match

Item 0 - wt:0 val:0

i\w	0	1	2	3	4
i=0	1	2	3	3	3

Updating dp[3] with max

Item 0 - wt:0 val:0

i\w	0	1	2	3	4
i=0	1	2	3	3	4

Updating dp[4] with match (final)

Item 0 - wt:0 val:4

i\w	0	1	2	3	4
i=0	1	2	3	3	4

Answer cell dp[4] = 4

Key Takeaways

✓ The dp array stores the longest palindromic subsequence length for substrings ending at each index, updated from right to left.

This insight is hard to see from code alone because the 1D dp array is reused and updated in place, making dependencies subtle.

✓ Matching characters extend palindrome length by 2 plus the palindrome length of the inner substring, while mismatches take the max of excluding one end.

Visualizing each update clarifies how the algorithm chooses between extending or skipping characters.

✓ The final answer is found in dp[n-1] after processing all substrings, representing the longest palindromic subsequence for the entire string.

Seeing the final dp array state and answer cell highlights the culmination of all subproblem solutions.

Practice

1. You are given two strings and need to find the shortest string that contains both as subsequences. Which algorithmic approach guarantees finding this shortest common supersequence efficiently?

easy

A. Greedy approach that merges characters from both strings whenever they differ

B. Dynamic programming based on longest common subsequence to build the shortest supersequence

C. Pure brute force recursion enumerating all supersequences and selecting the shortest

D. Sorting characters of both strings and merging them in lexicographical order

Solution

1. Step 1: Understand the problem requires minimal length supersequence containing both strings as subsequences

   Greedy or sorting approaches fail because they do not consider subsequence order constraints.

2. Step 2: Recognize that longest common subsequence (LCS) helps identify overlapping parts to minimize duplication

   Dynamic programming using LCS length allows building the shortest common supersequence efficiently.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   LCS-based DP is the classic and optimal approach for shortest common supersequence [OK]

Hint: Shortest common supersequence uses LCS-based DP [OK]

Common Mistakes:

• Thinking greedy merging always works
• Confusing substring with subsequence
• Assuming sorting helps

2. You need to determine if a given input string matches a pattern that may include '?' which matches any single character, and '*' which matches any sequence of characters (including empty). Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Dynamic Programming that builds a 2D table tracking matches between substrings of input and pattern

B. Pure brute force recursion trying all possible matches without memoization

C. Greedy matching by scanning both strings once, skipping characters when '*' is encountered

D. Sorting both strings and then comparing characters in order

Solution

1. Step 1: Understand problem constraints

   The pattern includes wildcards '?' and '*', which require checking multiple matching possibilities.

2. Step 2: Identify suitable algorithm

   Greedy or sorting approaches fail because '*' can match variable-length substrings; brute force is correct but inefficient. DP efficiently explores all subproblems with memoization.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP handles overlapping subproblems and wildcard flexibility [OK]

Hint: Wildcard matching requires DP, not greedy or sorting [OK]

Common Mistakes:

• Assuming greedy works for '*' wildcard
• Confusing brute force with DP
• Thinking sorting helps string matching with wildcards

3. Consider the following buggy code for the space-optimized edit distance. Which line contains the subtle bug that causes incorrect results for empty strings or boundary cases?

def minDistance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    dp = list(range(n + 1))
    for i in range(1, m + 1):
        prev = dp[0]
        dp[0] = 0  # Bug here
        for j in range(1, n + 1):
            temp = dp[j]
            if word1[i - 1] == word2[j - 1]:
                dp[j] = prev
            else:
                dp[j] = min(dp[j] + 1, dp[j - 1] + 1, prev + 1)
            prev = temp
    return dp[n]

medium

A. Line 4: dp = list(range(n + 1))

B. Line 6: prev = dp[0]

C. Line 7: dp[0] = 0 # Bug here

D. Line 11: dp[j] = min(dp[j] + 1, dp[j - 1] + 1, prev + 1)

Solution

1. Step 1: Understand dp[0] initialization role

   dp[0] represents cost of deleting all characters from word1 prefix to match empty word2 prefix, so it must be i, not 0.

2. Step 2: Identify incorrect dp[0] reset

   Setting dp[0] = 0 inside loop resets deletion cost incorrectly, breaking base case for empty prefixes.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Correct dp[0] update is dp[0] = i [OK]

Hint: dp[0] must track deletions, so dp[0] = i each iteration [OK]

Common Mistakes:

• Resetting dp[0] to zero
• Confusing prev and temp
• Misindexing dp array

4. Examine the following buggy code snippet for wildcard matching using space-optimized DP. Which line contains the subtle bug that causes incorrect results on empty strings or patterns?

medium

A. Line 14: curr[j] = curr[j - 1] or prev[j]

B. Line 10: curr = [False] * (n + 1) initialization

C. Line 6: prev[j] = True instead of prev[j] = prev[j - 1]

D. Line 17: curr[j] = prev[j - 1]

Solution

1. Step 1: Analyze initialization of prev array for '*' characters

   Line 6 sets prev[j] = True unconditionally when p[j-1] == '*', which incorrectly assumes all prefixes match.

2. Step 2: Correct initialization logic

   It should propagate previous state: prev[j] = prev[j - 1], ensuring '*' can match empty sequence only if previous prefix matched.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Incorrect initialization causes false positives on empty strings [OK]

Hint: Initialization must propagate previous True states for '*' [OK]

Common Mistakes:

• Setting prev[j] = True blindly
• Ignoring empty string edge cases
• Confusing '*' handling in initialization

5. The following code attempts to solve Word Break II using bottom-up DP. Identify the line containing the subtle bug that causes incorrect output with extra spaces in the sentences.

medium

A. Line: for word in word_set:

B. Line: sentences.append(word + " " + sentence)

C. Line: dp[n] = [""]

D. Line: if s.startswith(word, i):

Solution

1. Step 1: Examine string concatenation logic

   The line appends word + " " + sentence unconditionally, causing extra spaces when sentence is empty (base case).

2. Step 2: Identify fix

   Concatenate with space only if sentence is non-empty; otherwise append word alone to avoid trailing spaces.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Extra spaces come from unconditional space concatenation [OK]

Hint: Check concatenation when sentence is empty to avoid extra spaces [OK]

Common Mistakes:

• Forgetting base case empty string concatenation
• Misusing string concatenation in DP