Longest Common Subsequence

▶

Steps

setup

Initialize dp array

Create a dp array of length n+1 (4) initialized with zeros, representing LCS lengths with an empty prefix of text1.

💡 Starting with zeros means no characters matched yet; this array will be updated as we process text1.

Line:

dp = [0] * (n + 1)

💡 The dp array length corresponds to text2 length plus one, preparing to track subsequence lengths for all prefixes.

fill_row

Process text1 characters with outer and inner loops

For each character in text1, reset prev to 0 and iterate backwards through text2, updating dp array based on character matches or mismatches.

💡 Resetting prev at each outer loop iteration and updating dp backwards ensures correct subsequence length calculation.

Line:

for i in range(1, m + 1):
    prev = 0
    for j in range(n, 0, -1):
        temp = dp[j]
        if text1[i - 1] == text2[j - 1]:
            dp[j] = 1 + prev
        else:
            dp[j] = max(dp[j], dp[j - 1])
        prev = temp

💡 This nested loop structure incrementally builds the dp array representing LCS lengths.

compare

Compare 'a' with text2 characters and update dp

Compare text1[0] = 'a' with text2 characters from end to start: 'e', 'c', 'a'. Update dp accordingly.

💡 Matches increase dp[j], mismatches keep dp[j] as max of neighbors.

Line:

if text1[i - 1] == text2[j - 1]:
    dp[j] = 1 + prev
else:
    dp[j] = max(dp[j], dp[j - 1])

💡 First match found increases subsequence length to 1.

compare

Process second character 'b' of text1 and update dp

Compare 'b' with text2 characters 'e', 'c', 'a' in reverse order, updating dp array accordingly.

💡 No matches for 'b', but dp values may increase by taking max of neighbors.

Line:

if text1[i - 1] == text2[j - 1]:
    dp[j] = 1 + prev
else:
    dp[j] = max(dp[j], dp[j - 1])

💡 dp array reflects best subsequence length so far even without new matches.

compare

Process third character 'c' of text1 and update dp

Compare 'c' with text2 characters 'e', 'c', 'a' in reverse order, updating dp array accordingly.

💡 Match found at 'c' == 'c' increases dp[2] to 2.

Line:

if text1[i - 1] == text2[j - 1]:
    dp[j] = 1 + prev
else:
    dp[j] = max(dp[j], dp[j - 1])

💡 Subsequence length grows with matches and max propagation.

compare

Process fourth character 'd' of text1 and update dp

Compare 'd' with text2 characters 'e', 'c', 'a' in reverse order, updating dp array accordingly.

💡 No matches for 'd', dp values remain or increase by max of neighbors.

Line:

if text1[i - 1] == text2[j - 1]:
    dp[j] = 1 + prev
else:
    dp[j] = max(dp[j], dp[j - 1])

💡 dp array preserves best subsequence length without new matches.

compare

Process fifth character 'e' of text1 and update dp

Compare 'e' with text2 characters 'e', 'c', 'a' in reverse order, updating dp array accordingly.

💡 Match found at 'e' == 'e' increases dp[3] to 3.

Line:

if text1[i - 1] == text2[j - 1]:
    dp[j] = 1 + prev
else:
    dp[j] = max(dp[j], dp[j - 1])

💡 Final subsequence length reaches 3, the LCS length.

reconstruct

Return final answer dp[n]

After processing all characters, return dp[n] = dp[3] = 3 as the length of the longest common subsequence.

💡 The last dp cell holds the final LCS length.

Line:

return dp[n]

💡 The algorithm efficiently computes LCS length using a 1D dp array.

def lcs(text1, text2):
    m, n = len(text1), len(text2)
    dp = [0] * (n + 1)  # STEP 1: Initialize dp array
    for i in range(1, m + 1):  # STEP 2,4,5,6,7: Outer loop over text1
        prev = 0  # Reset prev
        for j in range(n, 0, -1):  # Inner loop backwards over text2
            temp = dp[j]  # Store current dp[j]
            if text1[i - 1] == text2[j - 1]:  # Compare chars
                dp[j] = 1 + prev  # Update dp[j] on match
            else:
                dp[j] = max(dp[j], dp[j - 1])  # Update dp[j] on mismatch
            prev = temp  # Update prev for next iteration
    return dp[n]  # STEP 8: Return final answer

print(lcs("abcde", "ace"))

📊

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

Watching each update to the dp array reveals how the algorithm uses previous computations to build the solution efficiently without storing the full 2D table.

Initializing dp array

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

dp initialized

Item 0 - wt:0 val:0

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

processing text1 chars

Item 0 - wt:0 val:1

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

'a' != 'e'

Item 1 - wt:0 val:1

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

'b' != 'e'

Item 2 - wt:0 val:2

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

'c' != 'e'

Item 3 - wt:0 val:2

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

'd' != 'e'

Item 4 - wt:0 val:3

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

'e' == 'e'

Item 4 - wt:0 val:3

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

final answer

Key Takeaways

✓ The 1D dp array is updated backwards to reuse space while preserving previous iteration values.

This is hard to see from code alone because the backward iteration and prev variable interplay is subtle.

✓ Matches between characters cause dp[j] to increase by 1 plus the previous dp[j-1] value from the prior iteration.

Visualizing this shows how subsequence length grows incrementally.

✓ When characters differ, dp[j] takes the max of dp[j] and dp[j-1], preserving the best subsequence length so far.

Seeing this decision repeatedly helps understand how the algorithm avoids losing progress.

Practice

1. Consider the following Python function implementing a space-optimized DP for longest common substring. What is the returned value when called with s1 = 'abc' and s2 = 'xbc'?

def longest_common_substring_space_optimized(s1, s2):
    n, m = len(s1), len(s2)
    dp = [0] * (m + 1)
    max_len = 0
    for i in range(1, n + 1):
        for j in range(m, 0, -1):
            if s1[i - 1] == s2[j - 1]:
                dp[j] = dp[j - 1] + 1
                if dp[j] > max_len:
                    max_len = dp[j]
            else:
                dp[j] = 0
    return max_len

easy

A. 2

B. 1

C. 3

D. 0

Solution

1. Step 1: Trace dp array updates for i=1 (s1[0]='a')

   Compare 'a' with 'c','b','x' in s2 backwards: no matches, dp remains zeros.

2. Step 2: Trace dp updates for i=2 (s1[1]='b') and i=3 (s1[2]='c')

   At i=2, j=2 matches 'b' == 'b', dp[2] = dp[1]+1=1; max_len=1. At i=3, j=3 matches 'c' == 'c', dp[3] = dp[2]+1=2; max_len=2.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Longest common substring is 'bc' length 2 [OK]

Hint: Trace dp updates backward to avoid overwriting [OK]

Common Mistakes:

• Iterating dp forward overwrites needed values
• Off-by-one indexing errors
• Confusing max_len update timing

2. Consider the following Python code for longest palindromic subsequence. What is the value of dp[4] after the outer loop iteration with i = 2 when input string is 'abba'?

easy

A. 3

B. 1

C. 2

D. 4

Solution

1. Step 1: Trace dp array before i=2 iteration

   Initially dp = [1,1,1,1]. After i=3 iteration, dp remains [1,1,1,1].

2. Step 2: Update dp for i=2 (s[2]='b')

   For j=3 (s[3]='a'), s[2]!=s[3], dp[3] = max(dp[3], dp[2]) = max(1,1)=1. So dp[3]=1. prev updated accordingly. dp array after iteration: dp=[1,1,1,1].

3. Step 3: Clarify indexing

   dp[4] is out of range since dp has indices 0 to 3. Assuming question means dp[3], the value is 1 after i=2 iteration.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   dp[3] after i=2 iteration is 1, matching 1 [OK]

Hint: Trace dp updates carefully with indices [OK]

Common Mistakes:

• Off-by-one indexing
• Confusing dp[j] and dp[j-1]
• Misunderstanding prev variable

3. The following code attempts to implement the space-optimized bottom-up DP for the Delete Operation for Two Strings problem. Which line contains a subtle bug that can cause incorrect results or index errors?

medium

A. Line 7: for i in range(m - 1, -1, -1):

B. Line 12: dp[j] = 1 + min(dp[j], dp[j + 1])

C. Line 10: if word1[j] == word2[j]:

D. Line 14: prev = temp

Solution

1. Step 1: Identify indices used in inner loop

   Inner loop iterates j over word2 indices; word1 index should be i, not j.

2. Step 2: Spot incorrect character comparison

   Line 10 compares word1[j] instead of word1[i], mixing indices causes wrong subproblem computations.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Correct index usage is critical for DP correctness [OK]

Hint: Check index variables carefully in nested loops [OK]

Common Mistakes:

• Mixing i and j indices
• Incorrect base case initialization
• Wrong iteration order

4. What is the time and space complexity of the space-optimized bottom-up DP solution for the interleaving string problem, where m and n are the lengths of s1 and s2 respectively?

medium

A. Time: O(m*n), Space: O(n)

B. Time: O(m*n), Space: O(m*n)

C. Time: O(2^(m+n)), Space: O(m+n)

D. Time: O(m+n), Space: O(m+n)

Solution

1. Step 1: Analyze time complexity

   The DP fills a table of size m*n (or simulates it with 1D array), so time is O(m*n).

2. Step 2: Analyze space complexity

   Space optimized approach uses a 1D dp array of size n+1, so space is O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP avoids exponential recursion and uses linear space in smaller dimension [OK]

Hint: DP table size dictates time; 1D dp array dictates space [OK]

Common Mistakes:

• Confusing recursion stack space with DP space
• Assuming full 2D dp array space is used in optimized version

5. Suppose the wildcard pattern matching problem is extended so that the '*' wildcard can match any sequence of characters, but now the input string can be infinitely long (streaming input). Which modification to the DP approach is necessary to handle this scenario efficiently?

hard

A. Switch to a greedy two-pointer approach that backtracks on '*' positions to avoid DP overhead

B. Use recursion with memoization caching all substring pairs to handle infinite input

C. Precompute all possible matches for '*' in advance and store in a lookup table

D. Use the same space-optimized DP with arrays sized by pattern length, processing input character by character

Solution

1. Step 1: Understand infinite input constraints

   DP requires O(m*n) time and space, not feasible for infinite input length.

2. Step 2: Identify suitable approach

   Greedy two-pointer with backtracking on '*' positions can process streaming input efficiently without full DP table.

3. Step 3: Why other options fail

   Precomputing or recursion with memoization is impossible with infinite input; DP arrays cannot grow infinitely.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Greedy with backtracking handles streaming input efficiently [OK]

Hint: Infinite input forbids DP; greedy with backtracking is needed [OK]

Common Mistakes:

• Trying DP on infinite input
• Assuming memoization works with infinite data
• Ignoring streaming constraints