Distinct Subsequences

🎯

Distinct Subsequences

hardDPGoogleFacebook

Imagine you want to find out how many different ways a secret message (target string) can be formed from a longer text (source string) by deleting some characters without changing the order.

💡 This problem asks for counting the number of distinct subsequences of one string that equal another string. Beginners often struggle because it requires understanding how to count combinations of subsequences rather than just checking existence, and naive recursion leads to exponential time.

📋

Problem Statement

Given two strings s and t, return the number of distinct subsequences of s which equals t. A subsequence of a string is a new string formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters.

1 ≤ s.length, t.length ≤ 10^5s and t consist of English letters.

💡

Example

Input"s = 'rabbbit', t = 'rabbit'"

Output3

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

Input"s = 'babgbag', t = 'bag'"

Output5

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

• Empty target string t → output should be 1 (empty subsequence)
• Empty source string s but non-empty t → output should be 0
• s and t are identical → output should be 1
• t longer than s → output should be 0

🔁

Why DP?

Why greedy fails:

A greedy approach might try to match characters from left to right and count matches, but it fails because multiple subsequences can overlap and skipping characters greedily misses counting all possibilities. For example, s='babgbag', t='bag' has multiple ways to form 'bag' that greedy misses.

DP state:

dp[i][j] represents the number of distinct subsequences of s[0..i-1] that equals t[0..j-1].

Recurrence:dp[i][j] = dp[i-1][j] + (s[i-1] == t[j-1] ? dp[i-1][j-1] : 0)

If current characters match, count subsequences including this match plus those excluding it; else only those excluding current s character.

⚠️

Common Mistakes

Not handling empty target string base case

Returns 0 instead of 1, missing that empty string is subsequence of any string

✅ Initialize dp[i][0] = 1 for all i or return 1 when j == len(t) in recursion

Iterating forwards in space optimized DP

Overwrites dp[j-1] before using it, leading to incorrect counts

✅ Iterate backwards on j in the inner loop

Using int instead of long/64-bit integer for large counts

Integer overflow causing wrong results for large inputs

✅ Use long/long long or BigInt depending on language

Confusing indices off-by-one in DP table

Index errors or incorrect results due to misaligned string and dp indices

✅ Carefully map dp indices to string indices with dp[i][j] representing s[:i], t[:j]

Not memoizing or caching results in recursion

Exponential time leading to TLE

✅ Add memoization cache keyed by indices

🧠

Brute Force (Pure Recursion)

💡 This approach helps understand the problem by exploring all subsequences explicitly, but it is inefficient due to repeated computations.

Intuition

Try all subsequences of s and count those that match t exactly by recursively deciding to include or exclude each character.

Algorithm

1. Define a recursive function that takes indices i, j for s and t respectively.
2. If j reaches end of t, return 1 (found a subsequence).
3. If i reaches end of s but j not end of t, return 0 (no subsequence).
4. If s[i] == t[j], recurse by including s[i] and excluding s[i], else recurse by excluding s[i].
5. Sum the counts from recursive calls.

💡 The recursion tree grows exponentially because each character in s branches into two choices, making it hard to track all paths.

Recurrence:count(i, j) = count(i+1, j) + (s[i] == t[j] ? count(i+1, j+1) : 0)

</>

Code

def numDistinct(s: str, t: str) -> int:
    def dfs(i, j):
        if j == len(t):
            return 1
        if i == len(s):
            return 0
        res = dfs(i+1, j)
        if s[i] == t[j]:
            res += dfs(i+1, j+1)
        return res

    return dfs(0, 0)

# Example usage
if __name__ == '__main__':
    print(numDistinct('rabbbit', 'rabbit'))  # Output: 3

Line Notes

def dfs(i, j):Defines recursive helper to explore subsequences starting at s[i], t[j]

if j == len(t):If target fully matched, count one valid subsequence

if i == len(s):If source exhausted but target not matched, no subsequence

res = dfs(i+1, j)Count subsequences skipping current s character

if s[i] == t[j]:If characters match, also count subsequences including current character

public class Solution {
    public int numDistinct(String s, String t) {
        return dfs(s, t, 0, 0);
    }

    private int dfs(String s, String t, int i, int j) {
        if (j == t.length()) return 1;
        if (i == s.length()) return 0;
        int res = dfs(s, t, i + 1, j);
        if (s.charAt(i) == t.charAt(j)) {
            res += dfs(s, t, i + 1, j + 1);
        }
        return res;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.numDistinct("rabbbit", "rabbit")); // 3
    }
}

Line Notes

public int numDistinct(String s, String t)Entry point calling recursive helper

if (j == t.length()) return 1;Target fully matched, count one subsequence

if (i == s.length()) return 0;Source exhausted without matching target

int res = dfs(s, t, i + 1, j);Count subsequences skipping current s character

if (s.charAt(i) == t.charAt(j))If characters match, count subsequences including current character

#include <iostream>
#include <string>
using namespace std;

class Solution {
public:
    int dfs(const string& s, const string& t, int i, int j) {
        if (j == t.size()) return 1;
        if (i == s.size()) return 0;
        int res = dfs(s, t, i + 1, j);
        if (s[i] == t[j]) {
            res += dfs(s, t, i + 1, j + 1);
        }
        return res;
    }

    int numDistinct(string s, string t) {
        return dfs(s, t, 0, 0);
    }
};

int main() {
    Solution sol;
    cout << sol.numDistinct("rabbbit", "rabbit") << endl; // 3
    return 0;
}

Line Notes

int dfs(const string& s, const string& t, int i, int j)Recursive helper exploring subsequences

if (j == t.size()) return 1;All target characters matched

if (i == s.size()) return 0;Source exhausted without full match

int res = dfs(s, t, i + 1, j);Count subsequences skipping current s character

if (s[i] == t[j])If characters match, count subsequences including current character

function numDistinct(s, t) {
    function dfs(i, j) {
        if (j === t.length) return 1;
        if (i === s.length) return 0;
        let res = dfs(i + 1, j);
        if (s[i] === t[j]) {
            res += dfs(i + 1, j + 1);
        }
        return res;
    }
    return dfs(0, 0);
}

console.log(numDistinct('rabbbit', 'rabbit')); // 3

Line Notes

function dfs(i, j)Recursive function to count subsequences from indices i, j

if (j === t.length) return 1;Target fully matched, count one subsequence

if (i === s.length) return 0;Source exhausted without matching target

let res = dfs(i + 1, j);Count subsequences skipping current s character

if (s[i] === t[j])If characters match, count subsequences including current character

⏱

Complexity

TimeO(2^n) where n = length of s

SpaceO(n) recursion stack depth

Each character in s branches into two recursive calls, leading to exponential growth.

💡 For n=20, this means over a million calls, which is impractical.

Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem structure.

🧠

Top-Down Memoization

💡 Memoization avoids recomputing the same subproblems by caching results, drastically improving efficiency over brute force.

Intuition

Store results of recursive calls in a cache keyed by indices to reuse them instead of recomputing.

Algorithm

1. Create a 2D cache initialized with -1 to indicate uncomputed states.
2. Modify the recursive function to check cache before computing.
3. If cached, return stored value; else compute and store in cache.
4. Return the cached result for each call.

💡 Memoization transforms exponential recursion into polynomial time by avoiding duplicate work.

Recurrence:dp[i][j] = dp[i+1][j] + (s[i] == t[j] ? dp[i+1][j+1] : 0)

</>

Code

def numDistinct(s: str, t: str) -> int:
    from functools import lru_cache

    @lru_cache(None)
    def dfs(i, j):
        if j == len(t):
            return 1
        if i == len(s):
            return 0
        res = dfs(i+1, j)
        if s[i] == t[j]:
            res += dfs(i+1, j+1)
        return res

    return dfs(0, 0)

# Example usage
if __name__ == '__main__':
    print(numDistinct('rabbbit', 'rabbit'))  # Output: 3

Line Notes

@lru_cache(None)Caches results of dfs calls to avoid recomputation

if j == len(t):Base case: target matched

if i == len(s):Base case: source exhausted

res = dfs(i+1, j)Count subsequences skipping current s character

if s[i] == t[j]:Count subsequences including current character if match

import java.util.*;

public class Solution {
    private Integer[][] memo;

    public int numDistinct(String s, String t) {
        memo = new Integer[s.length()][t.length()];
        return dfs(s, t, 0, 0);
    }

    private int dfs(String s, String t, int i, int j) {
        if (j == t.length()) return 1;
        if (i == s.length()) return 0;
        if (memo[i][j] != null) return memo[i][j];
        int res = dfs(s, t, i + 1, j);
        if (s.charAt(i) == t.charAt(j)) {
            res += dfs(s, t, i + 1, j + 1);
        }
        memo[i][j] = res;
        return res;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.numDistinct("rabbbit", "rabbit")); // 3
    }
}

Line Notes

private Integer[][] memo;Cache to store results of subproblems

if (memo[i][j] != null) return memo[i][j];Return cached result if available

int res = dfs(s, t, i + 1, j);Count subsequences skipping current s character

if (s.charAt(i) == t.charAt(j))Count subsequences including current character if match

memo[i][j] = res;Store computed result in cache

#include <iostream>
#include <string>
#include <vector>
using namespace std;

class Solution {
    vector<vector<int>> memo;
public:
    int dfs(const string& s, const string& t, int i, int j) {
        if (j == t.size()) return 1;
        if (i == s.size()) return 0;
        if (memo[i][j] != -1) return memo[i][j];
        int res = dfs(s, t, i + 1, j);
        if (s[i] == t[j]) {
            res += dfs(s, t, i + 1, j + 1);
        }
        memo[i][j] = res;
        return res;
    }

    int numDistinct(string s, string t) {
        memo.assign(s.size(), vector<int>(t.size(), -1));
        return dfs(s, t, 0, 0);
    }
};

int main() {
    Solution sol;
    cout << sol.numDistinct("rabbbit", "rabbit") << endl; // 3
    return 0;
}

Line Notes

vector<vector<int>> memo;2D cache for memoization

if (memo[i][j] != -1) return memo[i][j];Return cached result if computed

int res = dfs(s, t, i + 1, j);Count subsequences skipping current s character

if (s[i] == t[j])Count subsequences including current character if match

memo[i][j] = res;Cache the computed result

function numDistinct(s, t) {
    const memo = Array.from({ length: s.length }, () => Array(t.length).fill(-1));

    function dfs(i, j) {
        if (j === t.length) return 1;
        if (i === s.length) return 0;
        if (memo[i][j] !== -1) return memo[i][j];
        let res = dfs(i + 1, j);
        if (s[i] === t[j]) {
            res += dfs(i + 1, j + 1);
        }
        memo[i][j] = res;
        return res;
    }

    return dfs(0, 0);
}

console.log(numDistinct('rabbbit', 'rabbit')); // 3

Line Notes

const memo = Array.from({ length: s.length }, () => Array(t.length).fill(-1));Initialize 2D cache with -1

if (memo[i][j] !== -1) return memo[i][j];Return cached result if available

let res = dfs(i + 1, j);Count subsequences skipping current s character

if (s[i] === t[j])Count subsequences including current character if match

memo[i][j] = res;Store computed result in cache

⏱

Complexity

TimeO(n*m) where n = length of s, m = length of t

SpaceO(n*m) for memoization cache and recursion stack

Each subproblem (i,j) computed once and stored, reducing exponential calls to polynomial.

💡 For n=1000 and m=1000, this means about 1 million computations, which is feasible.

Interview Verdict: Accepted

This approach is efficient enough for large inputs and is a common interview solution.

🧠

Bottom-Up Tabulation

💡 Tabulation builds the solution iteratively from smaller subproblems, avoiding recursion and making the process explicit and often easier to debug.

Intuition

Use a 2D dp table where dp[i][j] counts subsequences of s prefix i matching t prefix j, fill table row by row.

Algorithm

1. Initialize dp array of size (len(s)+1) x (len(t)+1) with zeros.
2. Set dp[i][0] = 1 for all i, since empty t is subsequence of any prefix of s.
3. Iterate i from 1 to len(s), j from 1 to len(t).
4. If s[i-1] == t[j-1], dp[i][j] = dp[i-1][j-1] + dp[i-1][j], else dp[i][j] = dp[i-1][j].
5. Return dp[len(s)][len(t)] as the final count.

💡 Filling the table row-wise ensures all needed subproblems are computed before use.

Recurrence:dp[i][j] = dp[i-1][j] + (s[i-1] == t[j-1] ? dp[i-1][j-1] : 0)

</>

Code

def numDistinct(s: str, t: str) -> int:
    m, n = len(s), len(t)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
        dp[i][0] = 1

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

    return dp[m][n]

# Example usage
if __name__ == '__main__':
    print(numDistinct('rabbbit', 'rabbit'))  # Output: 3

Line Notes

dp = [[0] * (n + 1) for _ in range(m + 1)]Create DP table with extra row and column for base cases

for i in range(m + 1): dp[i][0] = 1Empty target subsequence count is 1 for any prefix of s

dp[i][j] = dp[i - 1][j]Count subsequences excluding current s character

if s[i - 1] == t[j - 1]: dp[i][j] += dp[i - 1][j - 1]Add count including current character if match

return dp[m][n]Final answer is count for full strings

public class Solution {
    public int numDistinct(String s, String t) {
        int m = s.length(), n = t.length();
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 0; i <= m; i++) {
            dp[i][0] = 1;
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i - 1][j];
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] += dp[i - 1][j - 1];
                }
            }
        }

        return dp[m][n];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.numDistinct("rabbbit", "rabbit")); // 3
    }
}

Line Notes

int[][] dp = new int[m + 1][n + 1];DP table with extra row and column for base cases

dp[i][0] = 1;Empty target subsequence count is 1 for any prefix of s

dp[i][j] = dp[i - 1][j];Count subsequences excluding current s character

if (s.charAt(i - 1) == t.charAt(j - 1))Add count including current character if match

return dp[m][n];Final answer for full strings

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    int numDistinct(string s, string t) {
        int m = s.size(), n = t.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

        for (int i = 0; i <= m; i++) {
            dp[i][0] = 1;
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i - 1][j];
                if (s[i - 1] == t[j - 1]) {
                    dp[i][j] += dp[i - 1][j - 1];
                }
            }
        }

        return dp[m][n];
    }
};

int main() {
    Solution sol;
    cout << sol.numDistinct("rabbbit", "rabbit") << endl; // 3
    return 0;
}

Line Notes

vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));DP table with base initialization

dp[i][0] = 1;Empty target subsequence count is 1

dp[i][j] = dp[i - 1][j];Count subsequences excluding current s character

if (s[i - 1] == t[j - 1])Add count including current character if match

return dp[m][n];Final count for full strings

function numDistinct(s, t) {
    const m = s.length, n = t.length;
    const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

    for (let i = 0; i <= m; i++) {
        dp[i][0] = 1;
    }

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            dp[i][j] = dp[i - 1][j];
            if (s[i - 1] === t[j - 1]) {
                dp[i][j] += dp[i - 1][j - 1];
            }
        }
    }

    return dp[m][n];
}

console.log(numDistinct('rabbbit', 'rabbit')); // 3

Line Notes

const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));Initialize DP table with zeros

dp[i][0] = 1;Empty target subsequence count is 1

dp[i][j] = dp[i - 1][j];Count subsequences excluding current s character

if (s[i - 1] === t[j - 1])Add count including current character if match

return dp[m][n];Final count for full strings

⏱

Complexity

TimeO(n*m)

SpaceO(n*m)

We fill a 2D table of size (n+1)*(m+1) once.

💡 For n=1000 and m=1000, this means about 1 million operations, which is efficient.

Interview Verdict: Accepted

This is the standard DP solution preferred in interviews for clarity and efficiency.

🧠

Space Optimized Bottom-Up DP

💡 Since dp[i][j] depends only on dp[i-1][j] and dp[i-1][j-1], we can reduce space from 2D to 1D by iterating backwards on t.

Intuition

Use a 1D array to store counts for t prefixes and update it as we iterate through s, carefully iterating backwards to preserve dependencies.

Algorithm

1. Initialize a 1D dp array of length n+1 with dp[0] = 1.
2. Iterate over s characters from i=1 to m.
3. For each s[i-1], iterate j from n down to 1.
4. If s[i-1] == t[j-1], update dp[j] += dp[j-1].
5. Return dp[n] as the final count.

💡 Backward iteration ensures dp[j-1] from previous iteration is used before dp[j] is updated.

Recurrence:dp[j] = dp[j] + (s[i-1] == t[j-1] ? dp[j-1] : 0)

</>

Code

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

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

    return dp[n]

# Example usage
if __name__ == '__main__':
    print(numDistinct('rabbbit', 'rabbit'))  # Output: 3

Line Notes

dp = [0] * (n + 1)Initialize 1D DP array for counts

dp[0] = 1Empty target subsequence count is 1

for j in range(n, 0, -1)Iterate backwards to preserve dp[j-1] before update

if s[i - 1] == t[j - 1]: dp[j] += dp[j - 1]Add counts including current character if match

return dp[n]Final count for full target string

public class Solution {
    public int numDistinct(String s, String t) {
        int m = s.length(), n = t.length();
        int[] dp = new int[n + 1];
        dp[0] = 1;

        for (int i = 1; i <= m; i++) {
            for (int j = n; j >= 1; j--) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[j] += dp[j - 1];
                }
            }
        }

        return dp[n];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.numDistinct("rabbbit", "rabbit")); // 3
    }
}

Line Notes

int[] dp = new int[n + 1];1D DP array to save space

dp[0] = 1;Empty target subsequence count is 1

for (int j = n; j >= 1; j--)Backward iteration to avoid overwriting needed values

if (s.charAt(i - 1) == t.charAt(j - 1))Add counts including current character if match

return dp[n];Final count for full target

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    int numDistinct(string s, string t) {
        int m = s.size(), n = t.size();
        vector<int> dp(n + 1, 0);
        dp[0] = 1;

        for (int i = 1; i <= m; i++) {
            for (int j = n; j >= 1; j--) {
                if (s[i - 1] == t[j - 1]) {
                    dp[j] += dp[j - 1];
                }
            }
        }

        return dp[n];
    }
};

int main() {
    Solution sol;
    cout << sol.numDistinct("rabbbit", "rabbit") << endl; // 3
    return 0;
}

Line Notes

vector<int> dp(n + 1, 0);1D DP array initialized with zeros

dp[0] = 1;Empty target subsequence count is 1

for (int j = n; j >= 1; j--)Backward iteration to preserve dp[j-1]

if (s[i - 1] == t[j - 1])Add counts including current character if match

return dp[n];Final count for full target string

function numDistinct(s, t) {
    const m = s.length, n = t.length;
    const dp = new Array(n + 1).fill(0);
    dp[0] = 1;

    for (let i = 1; i <= m; i++) {
        for (let j = n; j >= 1; j--) {
            if (s[i - 1] === t[j - 1]) {
                dp[j] += dp[j - 1];
            }
        }
    }

    return dp[n];
}

console.log(numDistinct('rabbbit', 'rabbit')); // 3

Line Notes

const dp = new Array(n + 1).fill(0);Initialize 1D DP array

dp[0] = 1;Empty target subsequence count is 1

for (let j = n; j >= 1; j--)Backward iteration to avoid overwriting dp[j-1]

if (s[i - 1] === t[j - 1])Add counts including current character if match

return dp[n];Return final count

⏱

Complexity

TimeO(n*m)

SpaceO(m)

We use a single array of length m and update it for each character in n.

💡 This reduces memory usage drastically while maintaining time efficiency.

Interview Verdict: Accepted

This is the most optimized DP solution in terms of space and is ideal for interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 Use memoization or bottom-up DP in 95% of interviews; space optimized DP is ideal if asked for memory efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n)	O(n) recursion stack	Yes (deep recursion)	N/A	Mention only - never code
2. Top-Down Memoization	O(n*m)	O(n*m) memo + recursion stack	Possible but less likely	Yes with extra tracking	Good for quick optimization of brute force
3. Bottom-Up Tabulation	O(n*m)	O(n*m)	No	Yes with path tracking	Preferred for clarity and iterative solution
4. Space Optimized DP	O(n*m)	O(m)	No	No (without extra work)	Best for memory constrained scenarios

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify the problem and constraints.Explain the brute force recursive approach to show understanding.Introduce memoization to optimize recursion.Present bottom-up DP for clarity and iterative solution.Finally, discuss space optimization for best performance.

Time Allocation

Clarify: 3min → Brute Force: 5min → Memoization: 7min → Tabulation: 7min → Space Optimization: 5min → Testing: 3min. Total ~30min

What the Interviewer Tests

Understanding of recursion and DP, ability to optimize naive solutions, and clarity in explaining tradeoffs.

Common Follow-ups

• What if the strings are very long? → Use space optimized DP.
• Can you reconstruct one subsequence? → Use DP with path reconstruction.
• What if characters are case insensitive? → Normalize strings before DP.
• How to handle very large counts? → Use modulo arithmetic.

💡 These follow-ups test your ability to adapt solutions and handle practical constraints.

🔍

Pattern Recognition

When to Use

1) Counting subsequences or ways, 2) Two strings involved, 3) Order matters but characters can be skipped, 4) Overlapping subproblems with optimal substructure

Signature Phrases

number of distinct subsequencescount the wayssubsequence formed by deleting characters

NOT This Pattern When

Substring problems (contiguous sequences) or problems without counting distinct ways

Similar Problems

Longest Common Subsequence - related by subsequence matchingEdit Distance - related by string transformationsUnique Paths - related by counting ways in grid

Practice

1. You are given two strings and want to find the minimum number of delete operations needed to make them equal. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Dynamic Programming based on Longest Common Subsequence (LCS)

B. Greedy approach deleting mismatched characters as soon as found

C. Pure brute force recursion without memoization

D. Sorting both strings and comparing characters sequentially

Solution

1. Step 1: Understand problem requires minimal deletions to equalize strings

   This is equivalent to finding the longest common subsequence (LCS) and deleting characters not in it.

2. Step 2: Recognize DP approach based on LCS guarantees optimal solution

   Greedy or sorting approaches fail because they do not consider subsequence order; brute force is correct but inefficient.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   LCS-based DP is classic for minimal delete operations [OK]

Hint: Minimal deletes -> LCS-based DP [OK]

Common Mistakes:

• Thinking greedy deletion works optimally
• Ignoring subsequence order
• Confusing sorting with subsequence

2. Consider the following code snippet for finding the longest palindromic substring using dynamic programming. What is the value of max_len after processing the input s = "abba"?

easy

A. 1

B. 3

C. 2

D. 4

Solution

1. Step 1: Trace dp for input "abba"

   Single chars dp[i][i] = True, max_len=1. For length=2, "ab" dp[0][1]=False, "bb" dp[1][2]=True, max_len=2. For length=3, "abb" dp[0][2]=False, "bba" dp[1][3]=False. For length=4, "abba" dp[0][3]=True (since s[0]==s[3] and dp[1][2]=True), max_len=4.

2. Step 2: Confirm max_len update

   max_len updated to 2 at "bb", then to 4 at "abba".

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Longest palindrome is "abba" length 4 [OK]

Hint: Check dp updates for length 4 substring "abba" [OK]

Common Mistakes:

• Off-by-one errors in length calculation
• Missing even length palindrome updates
• Confusing max_len update condition

3. The following code attempts to implement space-optimized DP for regex matching. Which line contains a subtle bug that causes incorrect results on some inputs?

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]

medium

A. Line: dp[0] = False inside the outer loop

B. Line: for j in range(1, n + 1): iterating forwards instead of backwards

C. Line: prev = dp[0] before inner loop starts

D. Line: dp[j] = dp[j] or dp[j - 2] inside the '*' handling block

Solution

1. Step 1: Understand dp array update dependencies

   When updating dp[j], dp[j - 2] must not be overwritten before use. Iterating forwards overwrites dp[j - 2] too early.

2. Step 2: Identify iteration direction bug

   Iterating forwards causes dp[j - 2] to be stale or overwritten, leading to incorrect matches. Iterating backwards avoids this.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Known bug in space-optimized regex DP is forward iteration [OK]

Hint: DP updates with '*' require backward iteration to preserve dp[j-2] [OK]

Common Mistakes:

• Assuming forward iteration is safe in space-optimized DP

4. The following code attempts to implement the space-optimized DP for maximum uncrossed lines. Which line contains a subtle bug that can cause incorrect results?

medium

A. Line 7: temp = dp[j]

B. Line 12: prev = temp

C. Line 11: dp[j] = max(dp[j], dp[j - 1])

D. Line 9: dp[j] = dp[j - 1] + 1

Solution

1. Step 1: Understand role of prev variable

   In space-optimized DP, dp[j] depends on prev (dp[j-1] from previous iteration), not dp[j-1] of current iteration.

2. Step 2: Identify incorrect dp update

   Line 9 uses dp[j - 1] from current iteration, which may have been updated already, causing incorrect results. It should use prev instead.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Using dp[j-1] instead of prev breaks correctness in space-optimized DP [OK]

Hint: Use prev to avoid overwriting dp[j-1] before use [OK]

Common Mistakes:

• Using dp[j-1] instead of prev in update
• Not preserving previous dp[j] value before update

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