Distinct Subsequences

📋

Distinct Subsequences

Edge cases:

</>

IDE

def numDistinct(s: str, t: str) -> int:public int numDistinct(String s, String t)int numDistinct(string s, string t)function numDistinct(s, t)

def numDistinct(s: str, t: str) -> int:
    # Write your solution here
    pass

class Solution {
    public int numDistinct(String s, String t) {
        // Write your solution here
        return 0;
    }
}

#include <string>
using namespace std;

int numDistinct(string s, string t) {
    // Write your solution here
    return 0;
}

function numDistinct(s, t) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Not counting subsequences when target is empty or missing base case dp[i][0] = 1.✅ Initialize dp[i][0] = 1 for all i to count empty subsequence correctly.

Wrong: 1Returning 1 when source is empty but target is non-empty.✅ Return 0 when s is empty and t is non-empty by setting dp[0][j] = 0 for j > 0.

Wrong: 1Greedy approach counting only one subsequence for repeated characters.✅ Sum dp[i-1][j] and dp[i-1][j-1] when characters match to count all combinations.

Wrong: Non-zeroConfusing 0/1 knapsack with unbounded, allowing reuse of characters multiple times.✅ Advance indices properly to prevent reuse of characters in subsequence counting.

Wrong: Non-zeroNot checking length constraints, returning counts when target longer than source.✅ Return 0 immediately if len(t) > len(s).

✓

Test Cases

Focus on handling empty strings and exact matches as base cases.

Watch out for greedy traps and ensure correct counting of repeated characters.

Optimize your DP to run efficiently on large inputs.

t1_01basic

Input{"s":"rabbbit","t":"rabbit"}

Expected3

⏱ Performance - must finish in 2000ms

There are 3 ways to form 'rabbit' from 'rabbbit' by deleting characters: different deletions of the extra 'b'.

💡 Think about matching characters from the end and counting subsequences.

💡 Use dynamic programming to count ways to form prefixes of t from prefixes of s.

💡 dp[i][j] = dp[i-1][j] + (dp[i-1][j-1] if s[i-1] == t[j-1] else 0).

Why it failed: Incorrect count likely due to missing the addition of dp[i-1][j-1] when characters match. Fix by adding dp[i-1][j-1] to dp[i-1][j] in that case. This is the canonical example test.

✓ Correctly counts all distinct subsequences matching t.

t1_02basic

Input{"s":"babgbag","t":"bag"}

Expected5

⏱ Performance - must finish in 2000ms

There are 5 distinct subsequences of 'babgbag' that equal 'bag'.

💡 Count subsequences by considering each character match and skipping.

💡 Use a DP table where dp[i][j] counts ways to form t[:j] from s[:i].

💡 Add dp[i-1][j-1] when s[i-1] == t[j-1], else carry dp[i-1][j].

Why it failed: Wrong output often caused by not accumulating counts properly when characters match. Fix by summing dp[i-1][j] and dp[i-1][j-1] when s[i-1] == t[j-1].

✓ Correctly accumulates counts for all subsequences.

t2_01edge

Input{"s":"abc","t":""}

Expected1

⏱ Performance - must finish in 2000ms

Empty target string t means one subsequence: empty subsequence.

💡 What is the number of ways to form an empty string from any string?

💡 Base case: dp[i][0] = 1 for all i.

💡 Return 1 when t is empty regardless of s.

Why it failed: Returning 0 or other value for empty t is wrong. Fix by initializing dp[i][0] = 1 for all i. This is the empty target string test.

✓ Correctly returns 1 for empty target string.

t2_02edge

Input{"s":"","t":"a"}

Expected0

⏱ Performance - must finish in 2000ms

Empty source string s cannot form any non-empty target t.

💡 If s is empty but t is not, no subsequences can match.

💡 Base case: dp[0][j] = 0 for j > 0.

💡 Return 0 when s is empty and t is non-empty.

Why it failed: Returning non-zero for empty s and non-empty t is incorrect. Fix by setting dp[0][j] = 0 for j > 0. This is the empty source string test.

✓ Correctly returns 0 when source is empty and target is non-empty.

t2_03edge

Input{"s":"abc","t":"abc"}

Expected1

⏱ Performance - must finish in 2000ms

When s and t are identical, only one subsequence matches: the entire string.

💡 Check if the entire string matches exactly once.

💡 DP should count exactly one way when s == t.

💡 Ensure no double counting or missing subsequences.

Why it failed: Incorrect output here often means double counting or missing the exact match case. Fix by proper DP initialization and transitions. This is the identical strings test.

✓ Correctly returns 1 when s and t are identical.

t2_04edge

Input{"s":"abc","t":"abcd"}

Expected0

⏱ Performance - must finish in 2000ms

Target longer than source means no subsequence can match.

💡 If t is longer than s, return 0 immediately.

💡 DP base case: dp[i][j] = 0 if j > i.

💡 Check length constraints before DP.

Why it failed: Returning non-zero when t longer than s is wrong. Fix by returning 0 if len(t) > len(s). This is the length boundary test.

✓ Correctly returns 0 when target longer than source.

t3_01corner

Input{"s":"aaaaa","t":"aaa"}

Expected10

⏱ Performance - must finish in 2000ms

Number of ways to choose 3 'a's from 5 'a's is C(5,3) = 10.

💡 Repeated characters can lead to combinatorial counts.

💡 DP must count all combinations, not just greedy matches.

💡 Use dp to sum all ways, not just first matches.

Why it failed: Greedy approach fails here by counting only one subsequence. Fix by summing dp[i-1][j] and dp[i-1][j-1] when characters match. This is the greedy trap test.

✓ Correctly counts all combinations of repeated characters.

t3_02corner

Input{"s":"abcde","t":"ace"}

Expected1

⏱ Performance - must finish in 2000ms

Only one subsequence 'ace' can be formed from 'abcde'.

💡 Check subsequences skipping characters correctly.

💡 DP must not confuse 0/1 knapsack with unbounded choices.

💡 Ensure each character in s is used at most once per subsequence.

Why it failed: Confusing 0/1 vs unbounded leads to overcounting subsequences. Fix by advancing indices properly without reuse. This is the 0/1 constraint test.

✓ Correctly counts subsequences with no reuse of characters.

t3_03corner

Input{"s":"abc","t":"abcd"}

Expected0

⏱ Performance - must finish in 2000ms

Target longer than source means no subsequence can match.

💡 If t is longer than s, return 0 immediately.

💡 DP base case: dp[i][j] = 0 if j > i.

💡 Check length constraints before DP.

Why it failed: Returning non-zero when t longer than s is wrong. Fix by returning 0 if len(t) > len(s). This is the length boundary test.

✓ Correctly returns 0 when target longer than source.

t4_01performance

Input{"s":"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","t":"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, m=50, O(n*m) DP must complete within 2 seconds.

💡 Use bottom-up DP with space optimization.

💡 Avoid exponential brute force recursion.

💡 Use rolling arrays to reduce memory.

Why it failed: Brute force or naive recursion causes TLE. Fix by implementing O(n*m) DP with memoization or tabulation. This is the performance complexity test.

✓ Efficient DP solution runs within time limits.

Practice

1. You are given three strings s1, s2, and s3. Determine if s3 can be formed by interleaving the characters of s1 and s2 while preserving the order of characters in each string. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Pure brute force recursion without memoization to explore all character combinations

B. Greedy algorithm that picks characters from s1 or s2 whenever they match s3 sequentially

C. Dynamic Programming using a 2D table to track interleaving possibilities for prefixes of s1 and s2

D. Sorting all strings and then comparing if s3 is a merged sorted string of s1 and s2

Solution

1. Step 1: Understand problem constraints

   The problem requires preserving the order of characters from both s1 and s2 to form s3. This rules out greedy and sorting approaches.

2. Step 2: Identify suitable algorithm

   Dynamic Programming with a 2D table tracks whether prefixes of s1 and s2 can form prefixes of s3, guaranteeing an optimal solution.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   DP ensures all prefix combinations are checked systematically [OK]

Hint: Interleaving requires DP to track prefix matches [OK]

Common Mistakes:

• Assuming greedy works because characters match sequentially
• Thinking sorting helps preserve order

2. Consider the following Python function implementing the space-optimized DP for Minimum ASCII Delete Sum:

def minimumDeleteSum(s1: str, s2: str) -> int:
    m, n = len(s1), len(s2)
    dp = [0] * (n + 1)
    for j in range(1, n + 1):
        dp[j] = dp[j-1] + ord(s2[j-1])
    for i in range(1, m + 1):
        prev = dp[0]
        dp[0] += ord(s1[i-1])
        for j in range(1, n + 1):
            temp = dp[j]
            if s1[i-1] == s2[j-1]:
                dp[j] = prev
            else:
                dp[j] = min(dp[j] + ord(s1[i-1]), dp[j-1] + ord(s2[j-1]))
            prev = temp
    return dp[n]

print(minimumDeleteSum("sea", "eat"))

What is the final returned value for input s1 = "sea" and s2 = "eat"?

easy

A. 231

B. 197

C. 314

D. 259

Solution

1. Step 1: Initialize dp array for s2="eat"

   dp after first loop: dp=[0, 101('e'), 101+97('a')=198, 198+116('t')=314]

2. Step 2: Iterate over s1="sea" updating dp

   After processing 's': dp=[115, 101, 198, 314] After 'e': dp=[216, 115, 198, 314] After 'a': dp final dp[n]=231

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Matches known example output 231 [OK]

Hint: Trace dp array updates carefully for each character [OK]

Common Mistakes:

• Off-by-one errors in indexing dp or strings

3. Suppose you want to find the length of the longest common subsequence between two strings, but now characters from the second string can be reused multiple times. Which modification to the standard LCS algorithm correctly handles this scenario?

hard

A. Use the same DP but allow dp[j] to depend on dp[j] itself without decrementing j in inner loop

B. Change the inner loop to iterate forwards and update dp[j] using dp[j] and dp[j-1] to allow reuse

C. Use a greedy approach matching characters from left to right allowing reuse

D. Use a bottom-up DP with a 2D table but ignore previous matches to allow reuse

Solution

1. Step 1: Understand reuse impact

   Allowing reuse of characters in the second string means dp[j] can be updated based on dp[j] itself (not only dp[j-1]) and the inner loop must run forwards to propagate reuse correctly.

2. Step 2: Identify correct DP iteration

   Iterating forwards in the inner loop allows dp[j] to accumulate matches with reuse, unlike standard LCS which iterates backwards to avoid reuse.

3. Step 3: Evaluate other options

   Greedy fails to find optimal subsequence. Ignoring previous matches breaks DP correctness. Using 2D DP without reuse logic is insufficient.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Forward iteration in inner loop enables reuse of characters [OK]

Hint: Forward inner loop iteration enables reuse in DP [OK]

Common Mistakes:

• Using backward iteration preventing reuse
• Trying greedy approach
• Ignoring DP state dependencies

4. Suppose you want to find the longest common substring between two strings, but now substrings can be formed by reusing characters multiple times (i.e., characters can be repeated any number of times). Which modification to the DP approach correctly handles this variant?

hard

A. Use the same DP but allow dp[j] to accumulate without resetting to zero on mismatch

B. Modify DP to allow transitions from dp[j] and dp[j-1] to handle reuse, iterating forward over j

C. Use a suffix automaton or suffix trie data structure instead of DP

D. Apply longest common subsequence DP since reuse allows gaps and repeats

Solution

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

   Longest common substring with reuse breaks contiguity and requires allowing repeated matches.

2. Step 2: Modify DP to allow reuse by iterating forward and allowing dp[j] to build on itself

   Iterating forward over j and allowing dp[j] to depend on dp[j] and dp[j-1] enables reuse of characters multiple times.

3. Step 3: Recognize other options fail

   Resetting dp on mismatch breaks reuse, suffix automaton is complex but not DP, subsequence DP allows gaps but not reuse as described.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Forward iteration with reuse transitions correctly models repeated characters [OK]

Hint: Reuse requires forward iteration and dp[j] depending on itself [OK]

Common Mistakes:

• Not resetting dp breaks reuse
• Using subsequence DP incorrectly
• Ignoring iteration order for reuse

5. Suppose the problem is modified so that you want to find the minimum cuts for palindrome partitioning but now the input string can contain wildcard characters '?' that can match any single character. Which of the following approaches correctly adapts the optimal DP solution to handle wildcards?

hard

A. Replace all '?' with all possible characters and run DP multiple times, taking minimum cuts over all results

B. Precompute all palindrome substrings ignoring '?', then run DP as usual

C. Use pure recursion with memoization since DP cannot handle wildcards efficiently

D. Modify palindrome checks to treat '?' as matching any character during center expansions, keeping the same DP structure

Solution

1. Step 1: Understand wildcard impact on palindrome checks

   Wildcards '?' can match any character, so palindrome checks must be adapted to treat '?' as a match with any character.

2. Step 2: Adapt DP palindrome center expansion

   Modify the center expansion condition to allow s[left] == s[right] or either is '?', preserving O(n^2) time and DP structure.

3. Step 3: Evaluate other options

   Precomputing ignoring '?' is incorrect as it misses wildcard matches. Pure recursion is inefficient. Replacing '?' with all characters is exponential and impractical.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Adapting palindrome checks for '?' preserves DP correctness and efficiency [OK]

Hint: Adapt palindrome checks, keep DP structure for wildcards [OK]

Common Mistakes:

• Ignoring wildcard impact on palindrome checks
• Trying exponential brute force over all replacements
• Assuming DP cannot handle wildcards