LeetCode 115: Distinct Subsequences Solution in Python – A Step-by-Step Guide

What Is LeetCode 115: Distinct Subsequences?

In LeetCode 115: Distinct Subsequences, you’re given two strings: s (the source) and t (the target). Your task is to find the number of distinct subsequences in s that equal t. A subsequence is a sequence of characters from s that can be formed by picking characters in order (not necessarily consecutive), without reusing positions. For example, with s = "rabbbit" and t = "rabbit", there are 3 ways to form "rabbit" by choosing different combinations of the b letters.

Problem Statement

• Input: Two strings s and t.
• Output: An integer—the number of distinct subsequences of s that equal t.
• Rules:
• Subsequences maintain relative order but can skip characters.
• Each character in s can be used at most once per subsequence.

Constraints

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

Examples

• Input: s = "rabbbit", t = "rabbit"
• Output: 3
• Why: Ways are ra_bbit, rab_bit, rabb_it (using 3rd, 4th, or 5th b).
• Input: s = "babgbag", t = "bag"
• Output: 5
• Why: b_a_g___, b___g_a_, b____ag_, _a_g_a_, ____gag.
• Input: s = "a", t = "a"
• Output: 1
• Why: One match.

Understanding the Problem: Counting the Matches

To solve LeetCode 115: Distinct Subsequences in Python, we need to count how many unique ways we can pick characters from s to form t, respecting order and distinctness. A brute force approach—generating all subsequences of s and checking against t—is O(2^n), which explodes with strings up to 1000 characters. Instead, we’ll use:

• Best Solution (DP with 2D Array): O(m*n) time, O(m*n) space—builds a table of counts.
• Alternative Solution (Recursive with Memoization): O(m*n) time, O(m*n) space—explores paths with memory.

Let’s start with the Best Solution—dynamic programming—and break it down clearly.

Best Solution: Dynamic Programming with 2D Array

Why This Is the Best Solution

The DP with 2D array approach shines because it’s efficient—O(m*n) time and space—and straightforward once you see the pattern. It builds a table that tracks the number of subsequences for every prefix pair of s and t, avoiding redundant calculations. It’s like laying out a grid where each cell tells you how many ways you’ve found so far—perfect for scaling to 1000-character strings!

How It Works

Here’s the strategy:

• Step 1: Define the DP Table:
• dp[i][j] = number of distinct subsequences of s[0:i] that equal t[0:j].
• Rows = length of s + 1, Columns = length of t + 1.
• Step 2: Base Cases:
• dp[i][0] = 1 (empty t matches any prefix of s once—by picking nothing).
• dp[0][j] = 0 (empty s can’t match non-empty t), except dp[0][0] = 1.
• Step 3: Fill the Table:
• For each s[i-1] and t[j-1]:
• If they match (s[i-1] == t[j-1]):
• dp[i][j] = dp[i-1][j-1] + dp[i-1][j] (use this char + skip it).
• If they don’t:
• dp[i][j] = dp[i-1][j] (skip this char in s).
• Step 4: Result:
• dp[m][n] gives the total count.

Step-by-Step Example

Example: s = "rabbbit", t = "rabbit"

• Setup: m = 7, n = 6, dp[8][7].
• Initialize:
• dp[i][0] = 1 (empty t).
• dp[0][j] = 0 (empty s), dp[0][0] = 1.
• DP Table (partial):

"" r a b b i t "" 1 0 0 0 0 0 0 r 1 1 0 0 0 0 0 a 1 1 1 0 0 0 0 b 1 1 1 1 0 0 0 b 1 1 1 2 0 0 0 b 1 1 1 3 0 0 0 i 1 1 1 3 0 3 0 t 1 1 1 3 0 3 3

• Key Steps:
• s[0]=r, t[0]=r: dp[1][1] = dp[0][0] + dp[0][1] = 1 + 0 = 1.
• s[2]=b, t[2]=b: dp[3][3] = dp[2][2] + dp[2][3] = 1 + 0 = 1.
• s[3]=b, t[2]=b: dp[4][3] = dp[3][2] + dp[3][3] = 1 + 1 = 2.
• s[4]=b, t[2]=b: dp[5][3] = dp[4][2] + dp[4][3] = 1 + 2 = 3.
• s[6]=t, t[5]=t: dp[7][6] = dp[6][5] + dp[6][6] = 3 + 0 = 3.
• Result: dp[7][6] = 3.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained step-by-step:

Copy codeclass Solution:
    def numDistinct(self, s: str, t: str) -> int:
        # Step 1: Get lengths
        m, n = len(s), len(t)

        # Step 2: Initialize DP table
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m + 1):
            dp[i][0] = 1  # Empty t matches any s prefix

        # Step 3: Fill DP table
        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]

• Line 4: Get lengths of s and t.
• Line 7-9: Create dp table, set base case for empty t.
• Line 12-16: Fill table:
• Line 14: If characters match, add “use it” and “skip it” counts.
• Line 16: If no match, just skip current s char.
• Line 18: Return final count.
• Time Complexity: O(m*n)—fill table once.
• Space Complexity: O(m*n)—size of DP table.

This builds a counting grid with ease!

Alternative Solution: Recursive with Memoization

Why an Alternative Approach?

The recursive with memoization approach is a natural way to explore subsequences—O(m*n) time and space, using a top-down method. It’s like asking, “How many ways can I build t from here?” and remembering the answers. It’s elegant but trades space for clarity compared to DP.

How It Works

Here’s the plan:

• Step 1: Define recursive function count(i, j):
• Number of subsequences of s[i:] that equal t[j:].
• Step 2: Base Cases:
• j == len(t): 1 (matched all of t).
• i == len(s): 0 (no s left, t remains).
• Step 3: Recurrence:
• If s[i] == t[j]:
• Use s[i] (count(i+1, j+1)) + skip it (count(i+1, j)).
• Else:
• Skip s[i] (count(i+1, j)).
• Step 4: Memoize to avoid repeats.

Step-by-Step Example

Example: s = "rabbbit", t = "rabbit"

• count(0, 0):
• r == r: count(1, 1) + count(1, 0).
• count(1, 1):
• a == a: count(2, 2) + count(2, 1).
• count(2, 2):
• b == b: count(3, 3) + count(3, 2).
• count(3, 3):
• b == b: count(4, 4) + count(4, 3).
• count(4, 4):
• b == i: count(5, 4).
• count(5, 4):
• i == i: count(6, 5) + count(6, 4).
• count(6, 5):
• t == t: count(7, 6) + count(7, 5).
• count(7, 6):
• j == len(t): 1.
• Backtrack: Compute up to count(0, 0) = 3.

Code for Recursive Approach

Copy codeclass Solution:
    def numDistinct(self, s: str, t: str) -> int:
        memo = {}

        def count(i, j):
            if j == len(t):
                return 1
            if i == len(s):
                return 0
            if (i, j) in memo:
                return memo[(i, j)]

            if s[i] == t[j]:
                memo[(i, j)] = count(i + 1, j + 1) + count(i + 1, j)
            else:
                memo[(i, j)] = count(i + 1, j)
            return memo[(i, j)]

        return count(0, 0)

• Line 4: Memoization dictionary.
• Line 6-16: Recursive function:
• Line 7-10: Base cases.
• Line 12-15: Recurrence with memoization.
• Time Complexity: O(m*n)—each state computed once.
• Space Complexity: O(m*n)—memo table.

It’s a recursive explorer with a memory boost!

Comparing the Two Solutions

• DP with 2D Array (Best):
• Pros: O(m*n) time and space, iterative, clear table.
• Cons: More initial setup.
• Recursive with Memo (Alternative):
• Pros: O(m*n) time and space, intuitive recursion.
• Cons: Stack space, slightly less efficient.

DP wins for practicality.

Additional Examples and Edge Cases

• "a", "b": 0 (no match).
• "aaa", "a": 3 (three ways).
• "", "a": 0 (empty s).

Both handle these well.

Complexity Breakdown

• DP: Time O(m*n), Space O(m*n).
• Recursive: Time O(m*n), Space O(m*n).

DP’s iterative edge shines.

Key Takeaways

• DP: Build a counting table!
• Recursive: Explore with memory!
• Subsequences: Order matters, not position.
• Python Tip: Arrays simplify—see [Python Basics](/python/basics).

Final Thoughts: Count the Ways

LeetCode 115: Distinct Subsequences in Python is a string-counting gem. The DP approach lays it out efficiently, while recursive memoization offers a thoughtful journey. Want more DP challenges? Try LeetCode 1143: Longest Common Subsequence or LeetCode 72: Edit Distance. Ready to count? Head to Solve LeetCode 115 on LeetCode and tally those subsequences today!