Distinct Subsequences

We can solve this problem by using dynamic programming. We’ll create a 2D table, where dp[i][j] represents the number of distinct subsequences of the first i characters of s that equal the first j characters of t.

Here’s the implementation:

  1. Initialize a 2D table dp with dimensions (m+1) x (n+1), where m is the length of s, and n is the length of t.

  2. Set dp[0][0] = 1, since there is one way to form an empty subsequence.

  3. For the remaining cells, iterate through s and t, and fill the table based on the following logic:

    • If s[i-1] == t[j-1], then dp[i][j] = dp[i-1][j-1] + dp[i-1][j].
    • Otherwise, dp[i][j] = dp[i-1][j].

  4. Return dp[m][n], which will contain the result.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def numDistinct(self, 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):
                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]

        return dp[m][n]

Explanation:

  • The base case dp[i][0] = 1 represents that there is one way to form an empty subsequence from any prefix of s.
  • When s[i-1] == t[j-1], we can either include the current character in the subsequence or skip it. Therefore, we sum the two possibilities.
  • When s[i-1] != t[j-1], the current character in s cannot be part of the subsequence, so we just copy the previous value.

The code above takes O(m * n) time and O(m * n) space, where m and n are the lengths of s and t, respectively.

Can you help me with finding the isomorphism for the LeetCode ? Please provide a concise response and if an exact mapping is not possible, specify it as an approximate mapping. If the titles of the problems are the same, select a different problem. Also, explain the reasoning behind your selection. Don’t mention anything about your training cut off date. Provide the best possible answer. Do not repeat the same point. Mention which problem is simpler. If there are multiple isomorphic problem. Arrange them from simple to more complex to your best possible knowledge. Do not add Leetcode to the problem name. The response format is:

The problem can be mapped to

10 Prerequisite LeetCode Problems

“Distinct Subsequences” is a dynamic programming problem which requires good understanding of string and subsequence manipulations. Here are some simpler problems to build your understanding:

  1. “Subsequence” (LeetCode 392): This problem introduces the concept of subsequences.

  2. “Longest Common Subsequence” (LeetCode 1143): This problem involves finding common subsequences in two strings. It’s a slightly simpler problem that still requires dynamic programming.

  3. “Longest Palindromic Subsequence” (LeetCode 516): This problem also involves finding subsequences but adds an additional complexity in terms of finding the longest palindrome.

  4. “Shortest Common Supersequence” (LeetCode 1092): This problem is a slight extension of the Longest Common Subsequence problem.

  5. “Unique Substrings in Wraparound String” (LeetCode 467): This problem is about finding all unique substrings. It will help you build an intuition around substring problems.

  6. “Delete Operation for Two Strings” (LeetCode 583): This problem is a variation of the Longest Common Subsequence problem.

  7. “Minimum ASCII Delete Sum for Two Strings” (LeetCode 712): This problem is also a variation of the Longest Common Subsequence problem but involves string deletion operations.

  8. “Count Binary Substrings” (LeetCode 696): This problem helps you practice counting distinct substrings.

  9. “Count Different Palindromic Subsequences” (LeetCode 730): This problem involves counting unique palindromic subsequences.

  10. “Uncrossed Lines” (LeetCode 1035): This problem is similar to the Longest Common Subsequence problem but with a unique visual twist.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        m = len(s)
        n = 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[-1][-1]

Given two strings s and t, return the number of distinct subsequences of s which equals t.

The test cases are generated so that the answer fits on a 32-bit signed integer.

Example 1:

Input: s = “rabbbit”, t = “rabbit” Output: 3 Explanation: As shown below, there are 3 ways you can generate “rabbit” from s. rabbbit rabbbit rabbbit

Example 2:

Input: s = “babgbag”, t = “bag” Output: 5 Explanation: As shown below, there are 5 ways you can generate “bag” from s. babgbag babgbag babgbag babgbag babgbag

Constraints:

1 <= s.length, t.length <= 1000 s and t consist of English letters.

Problem Classification

Distinct Subsequences - The problem involves counting the number of distinct subsequences of a string that equals another string. This requires understanding the properties of subsequences, hence the classification String Transformation Analysis / Subsequence Properties.

Distinct Subsequences - The problem involves counting the number of different parts of a text that equal another text. It’s about understanding the properties of parts of a text, thus Text Part Analysis.

Identifying Problem Isomorphism

Can you help me with finding the isomorphism for this problem?

Which problem does this problem map to the corresponding isomorphic problem on Leetcode ?

How did you identify that this problem is a variation of problem?

Language Agnostic Coding Drills

  1. Understanding Basic Data Structures (Lists in Python): The ability to create, manipulate and traverse through lists (or arrays in other languages) is a fundamental programming skill.

    Drill: Write a Python function to create a two-dimensional list (a list of lists) with given dimensions, and initialize it with a specific value.

  2. Nested Loops: This problem involves nested loops, which is a loop within a loop. It’s used in the code to iterate over the characters in two strings.

    Drill: Write a Python function that uses nested loops to traverse a two-dimensional list and print each element.

  3. Conditional Statements (if-else): This skill involves making decisions in the code based on certain conditions. Here, it is used to compare characters from two strings.

    Drill: Write a function that takes two strings as input, and returns a count of how many characters in the same position are the same in both strings.

  4. Dynamic Programming: This problem is a classic example of dynamic programming, where you break down a problem into simpler sub-problems, solve them, and use their solutions to construct the solution to the original problem.

    Drill: Write a function to solve a simple dynamic programming problem, such as finding the nth Fibonacci number. Start with a recursive solution, then add memoization, and finally convert it into a bottom-up dynamic programming solution.

Once you’ve practiced these drills, you can use these skills together to understand and implement the solution to this problem.

The problem is solved by creating a two-dimensional dynamic programming table dp, where dp[i][j] is the number of distinct subsequences of s[:i] that equals t[:j]. This table is populated by iterating through the strings s and t, updating dp[i][j] based on whether the current character in s equals the current character in t. If the characters are equal, dp[i][j] is incremented by dp[i-1][j-1] (the number of distinct subsequences of s[:i-1] that equals t[:j-1]). Whether the characters are equal or not, dp[i][j] is also incremented by dp[i-1][j] (the number of distinct subsequences of s[:i-1] that equals t[:j]). The answer to the problem is the final value in the table, dp[-1][-1].

Targeted Drills in Python

  1. Understanding Basic Data Structures (Lists in Python):
1
2
3
4
5

def create_2D_list(rows, cols, initial_value):
    return [[initial_value]*cols for _ in range(rows)]

# Usage
print(create_2D_list(3, 4, 0))
  1. Nested Loops:
1
2
3
4
5
6
7
8

def traverse_2D_list(matrix):
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            print(matrix[i][j], end=' ')
        print()

# Usage
traverse_2D_list([[1, 2, 3], [4, 5, 6], [7, 8, 9]])
  1. Conditional Statements (if-else):
1
2
3
4
5
6
7
8
9

def count_same_chars(str1, str2):
    count = 0
    for ch1, ch2 in zip(str1, str2):
        if ch1 == ch2:
            count += 1
    return count

# Usage
print(count_same_chars("hello", "hxllo"))
  1. Dynamic Programming:
1
2
3
4
5
6
7
8
9

# Fibonacci Series using Dynamic Programming
def fibonacci(n):
    fib = [0, 1] + [0]*(n-1)
    for i in range(2, n+1):
        fib[i] = fib[i-1] + fib[i-2]
    return fib[n]

# Usage
print(fibonacci(10))

Problem Specific Drill:

For this problem specifically, it would be useful to practice creating a dynamic programming table for string comparison problems.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def dp_table(str1, str2):
    m, n = len(str1), len(str2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(m+1):
        for j in range(n+1):
            if i == 0 or j == 0:
                dp[i][j] = 0
            elif str1[i-1] == str2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp

# Usage
print(dp_table("hello", "hxllo"))

This drill creates a dynamic programming table for the longest common subsequence problem. The function dp_table initializes a 2D list with m+1 rows and n+1 columns, where m and n are the lengths of str1 and str2 respectively. It then iterates over the characters in str1 and str2, updating dp[i][j] based on whether str1[i-1] equals str2[j-1]. The final table represents the lengths of the longest common subsequences of all prefixes of str1andstr2`.