Distinct Subsequences

▶

Steps

setup

Initialize dp array

We create a dp array of length n+1 (8) initialized with zeros, then set dp[0] = 1 because an empty target can be formed from any prefix of s by deleting all characters.

💡 Setting dp[0] = 1 is the base case that anchors all subsequence counts; it means there's exactly one way to form an empty string.

Line:

dp = [0] * (n + 1)
dp[0] = 1

💡 The dp array starts with dp[0] = 1 and zeros elsewhere, representing counts for empty target and no matches yet.

fill_row

Start outer loop: i=1 (s[0] = 'r')

We begin processing the first character 'r' of s. The dp array currently reflects counts for empty s prefix.

💡 Each iteration over s updates dp to count subsequences including the current character.

Line:

for i in range(1, m + 1):
    # i=1, s[i-1] = 'r'

💡 We are ready to update dp for the first character of s.

compare

Inner loop j=7 (t[6] = 't'), compare s[0]='r' and t[6]='t'

We compare s[0] = 'r' with t[6] = 't'. They do not match, so dp[7] remains unchanged.

💡 When characters don't match, dp[j] stays the same, meaning no new subsequences are added for this prefix.

Line:

for j in range(n, 0, -1):
    if s[i - 1] == t[j - 1]:
        dp[j] += dp[j - 1]

💡 No subsequences ending with 't' are formed from s[:1].

compare

Inner loop j=6 (t[5] = 'i'), compare s[0]='r' and t[5]='i'

Compare s[0] = 'r' with t[5] = 'i'. No match, dp[6] remains unchanged.

💡 Again, no match means no change to dp at this position.

Line:

if s[i - 1] == t[j - 1]:
    dp[j] += dp[j - 1]

💡 No new subsequences for prefix ending with 'i'.

compare

Inner loop j=5 (t[4] = 'b'), compare s[0]='r' and t[4]='b'

Compare s[0] = 'r' with t[4] = 'b'. No match, dp[5] unchanged.

💡 No match means dp[5] stays the same.

Line:

if s[i - 1] == t[j - 1]:
    dp[j] += dp[j - 1]

💡 No subsequences formed for this prefix.

compare

Inner loop j=4 (t[3] = 'b'), compare s[0]='r' and t[3]='b'

Compare s[0] = 'r' with t[3] = 'b'. No match, dp[4] unchanged.

💡 No match means no update.

Line:

if s[i - 1] == t[j - 1]:
    dp[j] += dp[j - 1]

💡 No subsequences added here.

compare

Inner loop j=3 (t[2] = 'b'), compare s[0]='r' and t[2]='b'

Compare s[0] = 'r' with t[2] = 'b'. No match, dp[3] unchanged.

💡 No update since characters differ.

Line:

if s[i - 1] == t[j - 1]:
    dp[j] += dp[j - 1]

💡 No subsequences formed here.

compare

Inner loop j=2 (t[1] = 'a'), compare s[0]='r' and t[1]='a'

Compare s[0] = 'r' with t[1] = 'a'. No match, dp[2] unchanged.

💡 No update since characters differ.

Line:

if s[i - 1] == t[j - 1]:
    dp[j] += dp[j - 1]

💡 No subsequences formed here.

compare

Inner loop j=1 (t[0] = 'r'), compare s[0]='r' and t[0]='r'

Compare s[0] = 'r' with t[0] = 'r'. They match, so we update dp[1] += dp[0]. dp[1] becomes 1.

💡 When characters match, we add the count of subsequences that formed the previous prefix to the current count.

Line:

if s[i - 1] == t[j - 1]:
    dp[j] += dp[j - 1]

💡 This shows how subsequences grow by matching characters.

fill_row

Start outer loop: i=2 (s[1] = 'a')

We move to the second character 'a' of s. The dp array now reflects counts after processing 'r'.

💡 Each new character in s can add new subsequences or extend existing ones.

Line:

for i in range(1, m + 1):
    # i=2, s[i-1] = 'a'

💡 We prepare to update dp for s[1] = 'a'.

compare

Inner loop j=7 (t[6] = 't'), compare s[1]='a' and t[6]='t'

Compare s[1] = 'a' with t[6] = 't'. No match, dp[7] unchanged.

💡 No update since characters differ.

Line:

if s[i - 1] == t[j - 1]:
    dp[j] += dp[j - 1]

💡 No new subsequences for this prefix.

compare

Inner loop j=6 (t[5] = 'i'), compare s[1]='a' and t[5]='i'

Compare s[1] = 'a' with t[5] = 'i'. No match, dp[6] unchanged.

💡 No update since characters differ.

Line:

if s[i - 1] == t[j - 1]:
    dp[j] += dp[j - 1]

💡 No new subsequences for this prefix.

compare

Inner loop j=5 (t[4] = 'b'), compare s[1]='a' and t[4]='b'

Compare s[1] = 'a' with t[4] = 'b'. No match, dp[5] unchanged.

💡 No update since characters differ.

Line:

if s[i - 1] == t[j - 1]:
    dp[j] += dp[j - 1]

💡 No new subsequences for this prefix.

compare

Inner loop j=4 (t[3] = 'b'), compare s[1]='a' and t[3]='b'

Compare s[1] = 'a' with t[3] = 'b'. No match, dp[4] unchanged.

💡 No update since characters differ.

Line:

if s[i - 1] == t[j - 1]:
    dp[j] += dp[j - 1]

💡 No new subsequences for this prefix.

compare

Inner loop j=3 (t[2] = 'b'), compare s[1]='a' and t[2]='b'

Compare s[1] = 'a' with t[2] = 'b'. No match, dp[3] unchanged.

💡 No update since characters differ.

Line:

if s[i - 1] == t[j - 1]:
    dp[j] += dp[j - 1]

💡 No new subsequences for this prefix.

compare

Inner loop j=2 (t[1] = 'a'), compare s[1]='a' and t[1]='a'

Compare s[1] = 'a' with t[1] = 'a'. They match, so dp[2] += dp[1]. dp[2] becomes 0 + 1 = 1.

💡 Matching characters add counts from previous prefix.

Line:

if s[i - 1] == t[j - 1]:
    dp[j] += dp[j - 1]

💡 Subsequences matching t[:2] now count 1.

compare

Inner loop j=1 (t[0] = 'r'), compare s[1]='a' and t[0]='r'

Compare s[1] = 'a' with t[0] = 'r'. No match, dp[1] unchanged.

💡 No update since characters differ.

Line:

if s[i - 1] == t[j - 1]:
    dp[j] += dp[j - 1]

💡 dp[1] remains 1.

fill_row

Start outer loop: i=3 (s[2] = 'b')

Process third character 'b' of s. dp array reflects counts after processing 'ra'.

💡 Each new character can add subsequences or extend existing ones.

Line:

for i in range(1, m + 1):
    # i=3, s[i-1] = 'b'

💡 Ready to update dp for s[2] = 'b'.

compare

Inner loop j=7 (t[6] = 't'), compare s[2]='b' and t[6]='t'

Compare s[2] = 'b' with t[6] = 't'. No match, dp[7] unchanged.

💡 No update since characters differ.

Line:

if s[i - 1] == t[j - 1]:
    dp[j] += dp[j - 1]

💡 dp[7] remains unchanged.

compare

Inner loop j=6 (t[5] = 'i'), compare s[2]='b' and t[5]='i'

Compare s[2] = 'b' with t[5] = 'i'. No match, dp[6] unchanged.

💡 No update since characters differ.

Line:

if s[i - 1] == t[j - 1]:
    dp[j] += dp[j - 1]

💡 dp[6] remains unchanged.

compare

Inner loop j=5 (t[4] = 'b'), compare s[2]='b' and t[4]='b'

Characters match, so dp[5] += dp[4]. dp[5] becomes 0 + 0 = 0 (no previous subsequences for dp[4]).

💡 Matching characters add counts from previous prefix.

Line:

if s[i - 1] == t[j - 1]:
    dp[j] += dp[j - 1]

💡 No subsequences yet for dp[4], so dp[5] stays 0.

compare

Inner loop j=4 (t[3] = 'b'), compare s[2]='b' and t[3]='b'

Characters match, dp[4] += dp[3]. dp[4] becomes 0 + 0 = 0 (dp[3] is 0 at this point).

💡 Matching characters add counts from previous prefix.

Line:

if s[i - 1] == t[j - 1]:
    dp[j] += dp[j - 1]

💡 No subsequences yet for dp[3], so dp[4] stays 0.

compare

Inner loop j=3 (t[2] = 'b'), compare s[2]='b' and t[2]='b'

Characters match, dp[3] += dp[2]. dp[3] becomes 0 + 1 = 1.

💡 This update shows subsequences forming for prefix t[:3].

Line:

if s[i - 1] == t[j - 1]:
    dp[j] += dp[j - 1]

💡 One subsequence matches t[:3] after processing s[:3].

compare

Inner loop j=2 (t[1] = 'a'), compare s[2]='b' and t[1]='a'

Characters differ, dp[2] unchanged.

💡 No update for non-matching characters.

Line:

if s[i - 1] == t[j - 1]:
    dp[j] += dp[j - 1]

💡 dp[2] remains 1.

compare

Inner loop j=1 (t[0] = 'r'), compare s[2]='b' and t[0]='r'

Characters differ, dp[1] unchanged.

💡 No update for non-matching characters.

Line:

if s[i - 1] == t[j - 1]:
    dp[j] += dp[j - 1]

💡 dp[1] remains 1.

reconstruct

Final step: Return dp[n]

After processing all characters, dp[7] holds the count of distinct subsequences of s that equal t. We return dp[7] = 3.

💡 The final dp value is the answer to the problem.

Line:

return dp[n]

💡 dp[7] = 3 means there are 3 distinct subsequences matching 'rabbit'.

def numDistinct(s: str, t: str) -> int:
    m, n = len(s), len(t)
    dp = [0] * (n + 1)  # STEP 1
    dp[0] = 1  # STEP 1

    for i in range(1, m + 1):  # STEP 2, 10, 14 ...
        for j in range(n, 0, -1):  # STEP 3-9, 11-13, 15-25 ...
            if s[i - 1] == t[j - 1]:  # STEP 3-9, 11-13, 15-25 ...
                dp[j] += dp[j - 1]  # STEP 9, 12, 16, 21, 22, 23 ...

    return dp[n]  # STEP 26

📊

Distinct Subsequences - Watch the Algorithm Execute, Step by Step

Watching each update to the dp array reveals how the algorithm counts distinct subsequences by building on previous counts, making the dynamic programming approach clear.

Item 0 - wt: val:

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

dp[0] = 1 (base case)

Item 0 - wt: val:

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

dp[0] = 1 (base)

Item 0 - wt: val:

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

'r' != 't', no update

Item 0 - wt: val:

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

'r' != 'i', no update

Item 0 - wt: val:

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

'r' != 'b', no update

Item 0 - wt: val:

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

'r' != 'b', no update

Item 0 - wt: val:

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

'r' != 'b', no update

Item 0 - wt: val:

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

'r' != 'a', no update

Item 0 - wt: val:

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

'r' == 'r', dp[1] += dp[0]

Item 1 - wt: val:

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

dp before i=2 updates

Item 1 - wt: val:

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

'a' != 't', no update

Item 1 - wt: val:

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

'a' != 'i', no update

Item 1 - wt: val:

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

'a' != 'b', no update

Item 1 - wt: val:

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

'a' != 'b', no update

Item 1 - wt: val:

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

'a' != 'b', no update

Item 1 - wt: val:

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

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

Item 1 - wt: val:

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

'a' != 'r', no update

Item 2 - wt: val:

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

dp before i=3 updates

Item 2 - wt: val:

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

'b' != 't', no update

Item 2 - wt: val:

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

'b' != 'i', no update

Item 2 - wt: val:

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

'b' == 'b', dp[5] += dp[4]

Item 2 - wt: val:

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

'b' == 'b', dp[4] += dp[3]

Item 2 - wt: val:

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

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

Item 2 - wt: val:

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

'b' != 'a', no update

Item 2 - wt: val:

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

'b' != 'r', no update

Item 6 - wt: val:

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

Answer dp[7] = 3

Key Takeaways

✓ The dp array accumulates counts of subsequences matching prefixes of t as we iterate through s.

This accumulation is hard to see from code alone but clear when watching dp updates step-by-step.

✓ Updating dp from right to left prevents overwriting values needed for current iteration.

This subtle detail ensures correctness and is visually evident when tracing each dp[j] update.

✓ Only when characters match do we add dp[j-1] to dp[j], showing how subsequences extend.

Seeing each comparison and update clarifies why non-matching characters leave dp unchanged.

Practice

1. Given the following code for computing edit distance, what is the value of dp[3] after the inner loop finishes when word1 = 'abc' and word2 = 'ac' during the second iteration of the outer loop (i=2)?

easy

A. 1

B. 0

C. 3

D. 2

Solution

1. Step 1: Trace dp array initialization and first iteration

   Initially dp = [0,1,2]. After i=1 (word1[0]='a'), dp updates to [1,0,1].

2. Step 2: Trace second iteration i=2 (word1[1]='b')

   Start dp[0]=2. For j=1 (word2[0]='a'), chars differ, dp[1]=min(0+1,2+1,1+1)=1. For j=2 (word2[1]='c'), chars differ, dp[2]=min(1+1,1+1,0+1)=1. So dp after inner loop: [2,1,1].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Manual step-by-step matches dp[3]=2 [OK]

Hint: Track dp updates carefully for each i,j iteration [OK]

Common Mistakes:

• Off-by-one indexing
• Confusing prev and temp variables
• Mis-updating dp[0]

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

3. Consider the following Python code for computing the length of the shortest common supersequence of two strings. What is the final returned value when calling scs_length("abac", "cab")?

easy

A. 5

B. 7

C. 6

D. 4

Solution

1. Step 1: Trace dp arrays for i=1 to 4 and j=1 to 3 with str1="abac", str2="cab"

   Initialize prev=[0,1,2,3]. For i=1 ('a'), update curr accordingly comparing with 'c','a','b'.

2. Step 2: Compute final dp row and return prev[n]

   After full iteration, prev[n] = 6, which is the length of the shortest common supersequence.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Manual dp tracing confirms final length is 6 [OK]

Hint: Trace dp arrays carefully to avoid off-by-one errors [OK]

Common Mistakes:

• Off-by-one indexing in loops
• Confusing i,j indices with string indices
• Miscomputing min values in dp

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

5. Suppose you want to compute the edit distance where characters can be replaced multiple times (reuse allowed) and the cost of replacement depends on character pairs. Which modification to the classic DP approach correctly handles this variant?

hard

A. Use bottom-up DP with a cost matrix for replacements and update dp accordingly

B. Modify DP to allow revisiting states multiple times with memoization

C. Switch to a greedy approach that picks cheapest replacement at each mismatch

D. Use the same DP but add a third dimension for replacement cost per character pair

Solution

1. Step 1: Understand replacement cost depends on character pairs

   Replacement cost varies, so DP must incorporate a cost matrix for each character pair.

2. Step 2: Adapt bottom-up DP to use cost matrix in dp updates

   When characters differ, dp[j] updates using the specific replacement cost from the matrix, ensuring correct minimal cost.

3. Step 3: Confirm approach handles reuse and varying costs

   Bottom-up DP with cost matrix correctly accumulates minimal costs allowing multiple replacements.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   DP with cost matrix handles variable replacement costs [OK]

Hint: Incorporate cost matrix into DP transitions for variable replacements [OK]

Common Mistakes:

• Adding extra DP dimension unnecessarily
• Using memoization without cost matrix
• Trying greedy which fails globally