Shortest Common Supersequence

▶

Steps

setup

Initialize prev array for empty str1 prefix

We initialize the prev array to represent the shortest supersequence lengths when str1 is empty. The values are simply the lengths of prefixes of str2, since the supersequence must include all characters of str2.

💡 This initialization sets the base case for the DP, showing how the algorithm handles empty substrings.

Line:

prev = list(range(n+1))

💡 The shortest supersequence length when str1 is empty is the length of str2 prefix considered.

fill_row

Start processing first character 'a' of str1

We begin the first iteration with i=1 (str1[0] = 'a'). Initialize curr array with curr[0] = i, representing shortest supersequence length when str2 is empty.

💡 Setting curr[0] = i reflects that when str2 is empty, the supersequence length equals the length of str1 prefix.

Line:

curr = [i] + [0]*n

💡 This sets the base for the current row, analogous to the prev array initialization.

compare

Compare str1[0] = 'a' and str2[0] = 'c'

Characters differ, so curr[1] is set to 1 plus the minimum of prev[1] (1) and curr[0] (1).

💡 When characters differ, we choose the shorter supersequence by either skipping a character from str1 or str2.

Line:

if str1[i-1] == str2[j-1]:
    curr[j] = 1 + prev[j-1]
else:
    curr[j] = 1 + min(prev[j], curr[j-1])

💡 The DP chooses the minimal extension to keep the supersequence shortest.

compare

Compare str1[0] = 'a' and str2[1] = 'a'

Characters match, so curr[2] is set to 1 plus prev[1] (1).

💡 Matching characters allow us to extend the supersequence by one without adding extra characters.

Line:

if str1[i-1] == str2[j-1]:
    curr[j] = 1 + prev[j-1]

💡 Matching characters reduce the supersequence length by reusing characters.

compare

Compare str1[0] = 'a' and str2[2] = 'b'

Characters differ, so curr[3] is set to 1 plus the minimum of prev[3] (3) and curr[2] (2).

💡 Choosing the minimal supersequence length by either skipping a character from str1 or str2.

Line:

else:
    curr[j] = 1 + min(prev[j], curr[j-1])

💡 The DP favors the shorter path to keep the supersequence minimal.

fill_row

Update prev to curr and start processing second character 'b' of str1

We assign prev = curr to prepare for the next iteration and initialize curr for i=2 with curr[0] = 2, representing shortest supersequence length when str2 is empty.

💡 This step moves the current row to previous, enabling reuse of computed values and sets base case for new row.

Line:

prev = curr
curr = [i] + [0]*n

💡 The DP arrays slide forward, maintaining only two rows for space optimization and foundation for next row computations.

compare

Compare str1[1] = 'b' and str2[0] = 'c'

Characters differ, so curr[1] = 1 + min(prev[1] (2), curr[0] (2)) = 3.

💡 Choosing minimal supersequence length by skipping a character.

Line:

else:
    curr[j] = 1 + min(prev[j], curr[j-1])

💡 The DP continues to build minimal supersequence lengths.

compare

Compare str1[1] = 'b' and str2[1] = 'a'

Characters differ, so curr[2] = 1 + min(prev[2] (2), curr[1] (3)) = 3.

💡 Choosing minimal supersequence length by skipping a character.

Line:

else:
    curr[j] = 1 + min(prev[j], curr[j-1])

💡 DP chooses the minimal extension again.

compare

Compare str1[1] = 'b' and str2[2] = 'b'

Characters match, so curr[3] = 1 + prev[2] (2) = 3.

💡 Matching characters allow extending supersequence without extra length.

Line:

if str1[i-1] == str2[j-1]:
    curr[j] = 1 + prev[j-1]

💡 Matching characters reduce supersequence length.

fill_row

Update prev to curr and start processing third character 'a' of str1

Assign prev = curr to prepare for next iteration and initialize curr for i=3 with curr[0] = 3.

💡 Sliding the DP window forward for space optimization and base case for new row.

Line:

prev = curr
curr = [i] + [0]*n

💡 Only two arrays are needed to compute the solution and foundation for third row computations.

compare

Compare str1[2] = 'a' and str2[0] = 'c'

Characters differ, so curr[1] = 1 + min(prev[1] (3), curr[0] (3)) = 4.

💡 Choosing minimal supersequence length.

Line:

else:
    curr[j] = 1 + min(prev[j], curr[j-1])

💡 DP continues minimal extension.

compare

Compare str1[2] = 'a' and str2[1] = 'a'

Characters match, so curr[2] = 1 + prev[1] (3) = 4.

💡 Matching characters reduce supersequence length.

Line:

if str1[i-1] == str2[j-1]:
    curr[j] = 1 + prev[j-1]

💡 Matching characters help keep supersequence short.

compare

Compare str1[2] = 'a' and str2[2] = 'b'

Characters differ, so curr[3] = 1 + min(prev[3] (3), curr[2] (4)) = 4.

💡 Choosing minimal supersequence length.

Line:

else:
    curr[j] = 1 + min(prev[j], curr[j-1])

💡 DP chooses minimal extension.

fill_row

Update prev to curr and start processing fourth character 'c' of str1

Assign prev = curr to prepare for next iteration and initialize curr for i=4 with curr[0] = 4.

💡 Sliding DP window forward and base case for last row.

Line:

prev = curr
curr = [i] + [0]*n

💡 Space optimization maintained and foundation for last row computations.

compare

Compare str1[3] = 'c' and str2[0] = 'c'

Characters match, so curr[1] = 1 + prev[0] (3) = 4.

💡 Matching characters reduce supersequence length.

Line:

if str1[i-1] == str2[j-1]:
    curr[j] = 1 + prev[j-1]

💡 Matching characters help keep supersequence short.

compare

Compare str1[3] = 'c' and str2[1] = 'a'

Characters differ, so curr[2] = 1 + min(prev[2] (4), curr[1] (4)) = 5.

💡 Choosing minimal supersequence length.

Line:

else:
    curr[j] = 1 + min(prev[j], curr[j-1])

💡 DP chooses minimal extension.

compare

Compare str1[3] = 'c' and str2[2] = 'b'

Characters differ, so curr[3] = 1 + min(prev[3] (4), curr[2] (5)) = 5.

💡 Choosing minimal supersequence length.

Line:

else:
    curr[j] = 1 + min(prev[j], curr[j-1])

💡 DP chooses minimal extension.

traverse

Return final shortest common supersequence length

The length of the shortest common supersequence is found in prev[n], which is prev[3] = 5.

💡 This final value represents the minimal length containing both strings as subsequences.

Line:

return prev[n]

💡 The DP arrays have computed the answer incrementally and efficiently.

def scs_length(str1, str2):
    m, n = len(str1), len(str2)
    prev = list(range(n+1))  # STEP 1: Initialize prev
    for i in range(1, m+1):  # STEP 2: Iterate over str1
        curr = [i] + [0]*n  # STEP 2: Initialize curr
        for j in range(1, n+1):  # STEP 3: Iterate over str2
            if str1[i-1] == str2[j-1]:  # STEP 4: Compare chars
                curr[j] = 1 + prev[j-1]  # STEP 5: Match case
            else:
                curr[j] = 1 + min(prev[j], curr[j-1])  # STEP 6: Mismatch case
        prev = curr  # STEP 7: Update prev
    return prev[n]  # STEP 8: Return answer

if __name__ == '__main__':
    print(scs_length("abac", "cab"))

📊

Shortest Common Supersequence - Watch the Algorithm Execute, Step by Step

Watching each update to the DP arrays reveals how overlapping subproblems build up the final solution, making the abstract code concrete and understandable.

Item 0 - wt:3 val:0

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

prev[0] = 0

Item 1 - wt:3 val:0

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

curr[0] = 1

Item 1 - wt:3 val:2

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

curr[1] = 2

Item 1 - wt:3 val:2

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

curr[2] = 2

Item 1 - wt:3 val:3

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

curr[3] = 3

Item 2 - wt:3 val:0

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

prev updated

Item 2 - wt:3 val:3

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

curr[1] = 3

Item 2 - wt:3 val:3

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

curr[2] = 3

Item 2 - wt:3 val:3

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

curr[3] = 3

Item 3 - wt:3 val:0

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

prev updated

Item 3 - wt:3 val:4

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

curr[1] = 4

Item 3 - wt:3 val:4

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

curr[2] = 4

Item 3 - wt:3 val:4

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

curr[3] = 4

Item 4 - wt:3 val:0

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

prev updated

Item 4 - wt:3 val:4

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

curr[1] = 4

Item 4 - wt:3 val:5

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

curr[2] = 5

Item 4 - wt:3 val:5

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

curr[3] = 5

Item 4 - wt:3 val:5

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

Answer = 5

Key Takeaways

✓ The DP arrays represent incremental solutions to subproblems, building up the shortest common supersequence length.

This insight is hard to see from code alone because the arrays are updated in place and the logic is implicit.

✓ Matching characters allow the supersequence length to increase by only one, reusing characters from both strings.

Visually seeing the match case highlights why the algorithm is efficient and avoids unnecessary length increases.

✓ When characters differ, the algorithm chooses the minimal extension by comparing previous row and current row values.

The trace shows concrete examples of this decision, clarifying the branching logic.

Practice

1. You need to determine if a given input string matches a pattern that includes '.' which matches any single character, and '*' which matches zero or more of the preceding element. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Dynamic Programming using a 2D table or space-optimized 1D array

B. Sorting the pattern and string then comparing character by character

C. Backtracking with pruning based on character classes

D. Greedy matching scanning the string once from left to right

Solution

1. Step 1: Understand problem constraints

   The pattern includes '*' which can match zero or more of the preceding element, and '.' which matches any single character. This requires checking multiple matching possibilities.

2. Step 2: Identify algorithmic approach

   Greedy or sorting approaches fail because '*' can match variable-length substrings and '.' matches any character. Backtracking is exponential in worst case. Dynamic Programming efficiently stores intermediate results to avoid recomputation, guaranteeing optimal solution.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP handles overlapping subproblems and variable-length matches [OK]

Hint: DP handles variable-length '*' matches optimally [OK]

Common Mistakes:

• Assuming greedy works for '*' patterns

2. You are given a string s and a dictionary of words. You need to find all possible sentences where s can be segmented into a sequence of dictionary words. Which approach guarantees finding all valid sentences efficiently without redundant recomputation?

easy

A. Dynamic programming with bottom-up tabulation and backtracking to build all sentences

B. Greedy algorithm that picks the longest matching word at each step

C. Pure brute force recursion without memoization

D. Top-down recursion without caching intermediate results

Solution

1. Step 1: Understand problem requirements

   The problem requires enumerating all possible valid sentences, not just checking existence or counting.

2. Step 2: Evaluate approaches

   Greedy fails because it may miss valid segmentations. Pure recursion without memoization leads to exponential recomputation. Top-down recursion without caching also recomputes subproblems. Bottom-up DP with backtracking efficiently builds all solutions by storing intermediate results.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bottom-up DP with backtracking enumerates all sentences efficiently [OK]

Hint: Bottom-up DP with backtracking enumerates all solutions [OK]

Common Mistakes:

• Thinking greedy or pure recursion suffices for all sentences

3. What is the time and space complexity of the space-optimized bottom-up DP solution for the maximum uncrossed lines problem, where the input arrays have lengths m and n respectively?

medium

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

B. Time: O(m+n), Space: O(m+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 complexity of outer and inner loops

   The algorithm uses two nested loops: outer loop runs m times, inner loop runs n times, resulting in O(m*n) time complexity.

2. Step 2: Check if recursion stack adds extra space

   Space is optimized to a single dp array of size n+1, so space complexity is O(n), not O(m*n) or O(m+n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Nested loops cause O(m*n) time; single dp array causes O(n) space [OK]

Hint: Nested loops -> O(m*n) time; single dp array -> O(n) space [OK]

Common Mistakes:

• Confusing recursion stack space with dp array space
• Assuming linear time due to optimization

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. Suppose you want to find the longest palindromic subsequence in a string where characters can be reused unlimited times. Which modification to the DP approach correctly handles this variant?

hard

A. Modify DP to consider infinite reuse by allowing i to stay fixed while j moves, and vice versa

B. Use a greedy approach selecting matching characters repeatedly from both ends

C. Use the same DP but allow indices i and j to move independently without restriction

D. This problem reduces to longest palindromic substring, so use Manacher's algorithm

Solution

1. Step 1: Understand reuse means characters can be counted multiple times

   Standard LPS counts each character once; reuse requires relaxing index movement constraints.

2. Step 2: Modify DP transitions to allow staying at i or j to reuse characters

   DP must consider cases where i or j does not advance to reuse characters, effectively allowing repeated use.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Allowing indices to stay or move independently models reuse correctly [OK]

Hint: Reuse means relaxing index movement in DP transitions [OK]

Common Mistakes:

• Using greedy approach
• Confusing substring with subsequence
• Applying substring algorithms incorrectly