Longest Common Substring

▶

Steps

setup

Initialize DP array and max_len

Create a DP array of length m+1 (6) initialized with zeros and set max_len to 0 before starting iterations.

💡 Initialization ensures we start with no common substrings counted and a clean DP array to build upon.

Line:

dp = [0] * (m + 1)
max_len = 0

💡 DP array length matches s2 length plus one for base case; max_len tracks longest substring found so far.

fill_row

Start outer loop: i=1 (s1[0] = 'a')

Begin processing the first character of s1 ('a'). The DP array will be updated for matches with s2 characters.

💡 Each iteration of i corresponds to fixing a character in s1 to compare against all s2 characters.

Line:

for i in range(1, n + 1):

💡 We focus on s1[0] and will update dp for all j from m down to 1.

fill_cells

Compare s1[0] and s2[4] ('a' vs 'e'), j=5

Compare characters 'a' (s1[0]) and 'e' (s2[4]). They do not match, so dp[5] is set to 0.

💡 When characters differ, the substring cannot continue here, so reset dp[j] to zero.

Line:

if s1[i - 1] == s2[j - 1]:
    dp[j] = dp[j - 1] + 1
else:
    dp[j] = 0

💡 Mismatch breaks any substring ending at these positions, so dp[5] resets.

fill_cells

Compare s1[0] and s2[3] ('a' vs 'c'), j=4

Compare 'a' and 'c'. They differ, so dp[4] is set to 0.

💡 Continuing backwards, mismatches reset dp cells to zero.

Line:

else:
    dp[j] = 0

💡 Mismatch resets dp[4], no substring continuation here.

fill_cells

Compare s1[0] and s2[2] ('a' vs 'f'), j=3

Compare 'a' and 'f'. They differ, so dp[3] is set to 0.

💡 Mismatch resets dp[3] to zero.

Line:

else:
    dp[j] = 0

💡 No substring continuation at dp[3].

fill_cells

Compare s1[0] and s2[1] ('a' vs 'b'), j=2

Compare 'a' and 'b'. They differ, so dp[2] is set to 0.

💡 Mismatch resets dp[2] to zero.

Line:

else:
    dp[j] = 0

💡 No substring continuation at dp[2].

fill_cells

Compare s1[0] and s2[0] ('a' vs 'a'), j=1

Characters match ('a' == 'a'), so dp[1] = dp[0] + 1 = 1. max_len updated to 1.

💡 Matching characters extend the substring length by 1.

Line:

if s1[i - 1] == s2[j - 1]:
    dp[j] = dp[j - 1] + 1
    if dp[j] > max_len:
        max_len = dp[j]

💡 DP array captures substring length ending at these indices.

fill_row

Start outer loop: i=2 (s1[1] = 'b')

Move to the second character of s1 ('b') to compare against s2 characters.

💡 Each new i iteration resets the context for substring matching with s1[i-1].

Line:

for i in range(1, n + 1):

💡 We will update dp array again for s1[1].

fill_cells

Compare s1[1] and s2[4] ('b' vs 'e'), j=5

Characters differ ('b' != 'e'), so dp[5] = 0.

💡 Mismatch resets dp[5].

Line:

else:
    dp[j] = 0

💡 No substring continuation at dp[5].

fill_cells

Compare s1[1] and s2[3] ('b' vs 'c'), j=4

Characters differ ('b' != 'c'), so dp[4] = 0.

💡 Mismatch resets dp[4].

Line:

else:
    dp[j] = 0

💡 No substring continuation at dp[4].

fill_cells

Compare s1[1] and s2[2] ('b' vs 'f'), j=3

Characters differ ('b' != 'f'), so dp[3] = 0.

💡 Mismatch resets dp[3].

Line:

else:
    dp[j] = 0

💡 No substring continuation at dp[3].

fill_cells

Compare s1[1] and s2[1] ('b' vs 'b'), j=2

Characters match ('b' == 'b'), so dp[2] = dp[1] + 1 = 2. max_len updated to 2.

💡 Matching characters extend the substring length; max_len updates to longest found so far.

Line:

if s1[i - 1] == s2[j - 1]:
    dp[j] = dp[j - 1] + 1
    if dp[j] > max_len:
        max_len = dp[j]

💡 Longest common substring length increases to 2 here.

fill_cells

Compare s1[1] and s2[0] ('b' vs 'a'), j=1

Characters differ ('b' != 'a'), so dp[1] = 0.

💡 Mismatch resets dp[1].

Line:

else:
    dp[j] = 0

💡 No substring continuation at dp[1].

fill_row

Start outer loop: i=3 (s1[2] = 'c')

Move to the third character of s1 ('c') to compare against s2 characters.

💡 Each new i iteration resets the context for substring matching with s1[i-1].

Line:

for i in range(1, n + 1):

💡 We will update dp array again for s1[2].

fill_cells

Compare s1[2] and s2[4] ('c' vs 'e'), j=5

Characters differ ('c' != 'e'), so dp[5] = 0.

💡 Mismatch resets dp[5].

Line:

else:
    dp[j] = 0

💡 No substring continuation at dp[5].

fill_cells

Compare s1[2] and s2[3] ('c' vs 'c'), j=4

Characters match ('c' == 'c'), so dp[4] = dp[3] + 1 = 1. max_len remains 2.

💡 Matching characters start a new substring or extend one if dp[3] > 0.

Line:

if s1[i - 1] == s2[j - 1]:
    dp[j] = dp[j - 1] + 1
    if dp[j] > max_len:
        max_len = dp[j]

💡 Substring length at dp[4] is 1, less than max_len.

fill_cells

Compare s1[2] and s2[2] ('c' vs 'f'), j=3

Characters differ ('c' != 'f'), so dp[3] = 0.

💡 Mismatch resets dp[3].

Line:

else:
    dp[j] = 0

💡 No substring continuation at dp[3].

fill_cells

Compare s1[2] and s2[1] ('c' vs 'b'), j=2

Characters differ ('c' != 'b'), so dp[2] = 0.

💡 Mismatch resets dp[2].

Line:

else:
    dp[j] = 0

💡 No substring continuation at dp[2].

fill_cells

Compare s1[2] and s2[0] ('c' vs 'a'), j=1

Characters differ ('c' != 'a'), so dp[1] = 0.

💡 Mismatch resets dp[1].

Line:

else:
    dp[j] = 0

💡 No substring continuation at dp[1].

reconstruct

Final step: Return max_len = 2

After all iterations, the maximum length of the longest common substring found is 2.

💡 The max_len variable holds the final answer after processing all characters.

Line:

return max_len

💡 The longest common substring length is 2, corresponding to 'ab'.

def longest_common_substring_space_optimized(s1, s2):
    n, m = len(s1), len(s2)
    dp = [0] * (m + 1)  # STEP 1: Initialize dp array
    max_len = 0  # STEP 1: Initialize max_len
    for i in range(1, n + 1):  # STEP 2,8,14: Outer loop over s1
        for j in range(m, 0, -1):  # STEP 3-7,9-13,15-19: Inner loop over s2 backwards
            if s1[i - 1] == s2[j - 1]:  # STEP 7,12,16: Check match
                dp[j] = dp[j - 1] + 1  # STEP 7,12,16: Update dp[j]
                if dp[j] > max_len:  # STEP 7,12: Update max_len
                    max_len = dp[j]
            else:
                dp[j] = 0  # STEP 3-6,9-11,13,15,17-19: Reset dp[j] on mismatch
    return max_len  # STEP 20: Return answer

if __name__ == '__main__':
    print(longest_common_substring_space_optimized('abcde', 'abfce'))  # Output: 2

📊

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

Watching each update to the DP array and the max length variable reveals how the algorithm efficiently finds the longest common substring without storing the entire 2D table.

Initializing dp array

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

initialized to 0

Item 0 - wt:0 val:0

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

Item 0 - wt:0 val:0

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

'a' != 'e', dp[5]=0

Item 0 - wt:0 val:0

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

'a' != 'c', dp[4]=0

Item 0 - wt:0 val:0

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

'a' != 'f', dp[3]=0

Item 0 - wt:0 val:0

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

'a' != 'b', dp[2]=0

Item 0 - wt:0 val:1

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

'a' == 'a', dp[1]=1

Item 1 - wt:0 val:0

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

Item 1 - wt:0 val:0

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

'b' != 'e', dp[5]=0

Item 1 - wt:0 val:0

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

'b' != 'c', dp[4]=0

Item 1 - wt:0 val:0

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

'b' != 'f', dp[3]=0

Item 1 - wt:0 val:2

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

'b' == 'b', dp[2]=2

Item 1 - wt:0 val:0

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

'b' != 'a', dp[1]=0

Item 2 - wt:0 val:0

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

Item 2 - wt:0 val:0

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

'c' != 'e', dp[5]=0

Item 2 - wt:0 val:1

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

'c' == 'c', dp[4]=1

Item 2 - wt:0 val:0

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

'c' != 'f', dp[3]=0

Item 2 - wt:0 val:0

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

'c' != 'b', dp[2]=0

Item 2 - wt:0 val:0

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

'c' != 'a', dp[1]=0

Initializing dp array

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

max_len = 2 (answer)

Key Takeaways

✓ The DP array stores lengths of longest common substrings ending at each position in s2 for the current character in s1.

This insight is hard to see from code alone because the 1D array updates backwards and depends on previous iteration values.

✓ Updating the DP array backwards preserves dependencies, allowing space optimization from 2D to 1D without losing correctness.

Visualizing the backward update clarifies why the algorithm avoids overwriting needed values.

✓ The max_len variable dynamically tracks the longest substring length found so far, updated only on matches.

Seeing max_len update alongside dp array changes concretely shows how the answer emerges during iteration.

Practice

1. Consider the following Python code implementing space-optimized DP for regex matching. What is the final return value when calling isMatch('aab', 'c*a*b')?

def isMatch(s: str, p: str) -> bool:
    m, n = len(s), len(p)
    dp = [False] * (n + 1)
    dp[0] = True
    for j in range(2, n + 1):
        if p[j - 1] == '*':
            dp[j] = dp[j - 2]
    for i in range(1, m + 1):
        prev = dp[0]
        dp[0] = False
        for j in range(1, n + 1):
            temp = dp[j]
            if p[j - 1] == '*':
                dp[j] = dp[j] or dp[j - 2]
                if p[j - 2] == '.' or p[j - 2] == s[i - 1]:
                    dp[j] = dp[j] or prev
            else:
                dp[j] = prev and (p[j - 1] == '.' or p[j - 1] == s[i - 1])
            prev = temp
    return dp[n]

print(isMatch('aab', 'c*a*b'))

easy

A. None

B. False

C. Raises IndexError

D. True

Solution

1. Step 1: Trace dp initialization for pattern 'c*a*b'

   dp[0] = True; dp[2] = dp[0] because p[1] = '*', dp[4] = dp[2] because p[3] = '*'

2. Step 2: Iterate over string 'aab' updating dp

   After processing all characters, dp[n] = dp[6] becomes True because 'c*' matches empty, 'a*' matches 'aa', and 'b' matches 'b'.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Known test case returns True [OK]

Hint: Pattern with '*' can match empty or multiple chars [OK]

Common Mistakes:

• Confusing dp indices or forgetting dp initialization for '*'

2. 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

3. 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

4. The following code attempts to find the longest palindromic substring using DP. Identify the line containing the subtle bug that causes incorrect results for some inputs.

medium

A. Line: if length < 3:

B. Line: dp[i][i] = True

C. Line: dp[i][j] = dp[i + 1][j - 1]

D. Line: for i in range(n - length + 1):

Solution

1. Step 1: Compare condition with correct code

   The correct condition is length <= 3, but here it is length < 3, so length=3 substrings are not handled correctly.

2. Step 2: Understand impact

   For length=3, dp[i][j] should be True if s[i]==s[j], but this code skips that, causing missed palindromes of length 3.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing < to <= fixes the bug [OK]

Hint: Check boundary conditions for length 3 palindromes [OK]

Common Mistakes:

• Off-by-one in length condition
• Confusing substring indices
• Incorrect DP table initialization

5. What is the time and space complexity of the space-optimized bottom-up DP solution for the Minimum ASCII Delete Sum problem, given strings of lengths m and n?

medium

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

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

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

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

Solution

1. Step 1: Identify nested loops

   Outer loop runs m times, inner loop runs n times -> total O(m*n) time.

2. Step 2: Analyze space usage

   Only one dp array of size n+1 is used, so space is O(n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Matches known DP optimization for string problems [OK]

Hint: Nested loops multiply time; dp array size defines space [OK]

Common Mistakes:

• Confusing recursion stack space with DP array space