Distinct Subsequences Leetcode Problem 115 [Python Solution]

If you've been delving into the world of dynamic programming and are ready to tackle a challenging problem, you're in the right place.

In this guide, we'll break down the LeetCode problem Distinct Subsequences (Problem 115) using Python.

We'll explore the problem statement, walk through a Python solution, discuss its time and space complexity, and explain the reasoning behind our approach.

Problem Overview

The Distinct Subsequences problem is all about finding the number of distinct subsequences of string s that match string t.

A subsequence is essentially a subset of characters from the original string, preserving the order of characters.

The goal is to determine how many ways we can obtain string t by selecting subsequences from string s.

Let's dive into an example to understand the problem better:

Example 1:

Input:

s = "rabbbit", t = "rabbit"


Output:

3


Explanation:

In this example, there are three distinct ways to generate the string "rabbit" from string s.

Here's how:

1. Using the first three characters of s: "rab" from "rabbbit."
2. Using the first four characters of s: "rabb" from "rabbit."
3. Using the first six characters of s: "rabbbit" from "rabbit."

Example 2:

Input:

s = "babgbag", t = "bag"


Output:

5


Explanation:

In this example, there are five distinct ways to obtain the string "bag" from string s.

Here's how:

1. Using the first, second, and fourth characters of s: "bag" from "babgbag."
2. Using the first, third, and fourth characters of s: "bag" from "babg**bag."
3. Using the first, second, and fifth characters of s: "bag" from "babgag."
4. Using the first, third, and fifth characters of s: "bag" from "babgag."
5. Using the first, fourth, and fifth characters of s: "bag" from "babgbag**."

Constraints:

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

Now that we've grasped the problem, let's break down how to efficiently solve it using Python.

Efficient Python Code Solution

We're going to tackle this problem using dynamic programming, specifically a top-down (recursive) approach.

We'll define a function that will help us count the number of distinct subsequences by considering two main cases:

1. If the characters at the current positions match, we can choose to either include the character in the subsequence or skip it.
2. If the characters don't match, we must skip the character in s and continue searching for a match.

Here's the Python code to solve this problem:

def numDistinct(s: str, t: str) -> int:
    # Initialize a cache to store computed results
    cache = {}

    # Helper function for depth-first search
    def dfs(i, j):
        # Base case 1: If t is empty, there is one way to match it (skip all characters in s).

if j == len(t):
            return 1

        # Base case 2: If s is empty and t is not, there's no way to match t.

if i == len(s):
            return 0

        # If the result for these indices is already cached, return it.

if (i, j) in cache:
            return cache[(i, j)]

        # If the characters at s[i] and t[j] match, we have two options:
        # 1. Include the character in the subsequence (move both i and j).
        # 2. Skip the character in s (move only i).

if s[i] == t[j]:
            result = dfs(i + 1, j + 1) + dfs(i + 1, j)
        else:
            # If characters don't match, we can only skip in s (move only i).

result = dfs(i + 1, j)

        # Cache the result for these indices and return it.

cache[(i, j)] = result
        return result

    # Start the depth-first search from the beginning of both strings.

return dfs(0, 0)

Let's break down the key components of this solution:

1. Cache

We use a dictionary (cache) to store already computed results, which helps us avoid redundant computations.

The keys in the cache are pairs (i, j) representing the current positions in strings s and t.

2. Depth-First Search (DFS)

The dfs function is our main recursive function.

It considers the current positions i in string s and j in string t.

It handles the base cases and computes the result based on the two cases mentioned earlier.

• Base Case 1: If j has reached the end of string t, it means we've successfully matched the entire t.

In this case, we return 1.
– Base Case 2: If i has reached the end of string s but t is not empty, there's no way to match t.

We return 0.
– Cached Results: Before doing any computation, we check if the result for the current positions (i, j) is already in the cache.

If it is, we return the cached result to avoid recomputation.

3. Matching Characters

If the characters at s[i] and t[j] match, we have two choices:
1. Include the character in the subsequence (increment both i and j).
2. Skip the character in s (increment only i).

4. Non-Matching Characters

If the characters at s[i] and t[j] don't match, we can only skip the character in s (increment only i).

5. Starting the DFS

We start the depth-first search from the beginning of both strings, with i and j initially set to 0. Now, let's discuss the time and space complexity of this solution.

Time and Space Complexity

Time Complexity

The time complexity of this solution is O(n * m), where n is the length of string s and m is the length of string t.

This is because we might have to calculate the result for each combination of positions (i, j) in the range of 0 to n and 0 to m.

However, the cache prevents us from recalculating the same results, so the actual number of computations is much lower in practice.

Space

Complexity

The space complexity is O(n * m) as well.

The cache dictionary stores the results for all combinations of positions (i, j) in the range of 0 to n and 0 to m.

Related Interview Questions By Company:

• Binary Tree Maximum Path Sum LeetCode
• Minimum Interval To Include Each Query LeetCode
• First Missing Positive LeetCode

Related Interview Questions By Difficulty:

• Longest Increasing Path In A Matrix LeetCode
• Ones And Zeroes LeetCode
• Count Vowels Permutation LeetCode

Related Interview Questions By Category:

• Design Twitter LeetCode
• Distinct Subsequences LeetCode

Reasoning Behind Our Approach

The reasoning behind this approach is based on the observation that we can break down the problem into smaller subproblems.

By considering different ways to match characters in s and t, we can compute the number of distinct subsequences that match t.

Using a cache to store intermediate results allows us to avoid redundant calculations and significantly improves the efficiency of the algorithm.

In this problem, dynamic programming provides an elegant and efficient solution to count distinct subsequences, and our top-down approach with a cache ensures we handle it effectively.

To summarize, the Distinct Subsequences problem can be efficiently solved using dynamic programming in Python, and our top-down approach provides an elegant solution.

We've covered the problem statement, presented the Python code, explained the time and space complexity, and discussed the reasoning behind our approach.

If you have any questions, feel free to ask or share your thoughts in the comments.

To further challenge yourself and explore more LeetCode problems, you can find this problem here.

Happy coding!

We encourage you to comment, ask questions, make suggestions, and share this content with others.

Your engagement helps us improve and provide more valuable content for the community.

Happy coding!