Distinct Subsequences

LeetCode 115: Distinct Subsequences Solution & Explanation

Problem Overview

TL;DR: Use dynamic programming to count how many ways each prefix of t can be formed from each processed prefix of s, storing the 2D state in a one-dimensional array updated from right to left.

In LeetCode 115, Distinct Subsequences, the task is to count index selections from s whose characters appear in order and spell t. Selected characters do not need to be adjacent, and two selections are different when they use different indices.

For example, if s = "aaaaa" and t = "aaa", selecting positions (0, 1, 2) differs from selecting (0, 1, 3), even though both selections produce the same string.

This is a popular interview question because it combines string processing, counting, and dynamic programming. The LeetCode 115 Solution uses a 2D-array dynamic programming state compressed into one dimension.

Brute Force Approach for Distinct Subsequences

A direct approach considers every character in s and decides whether to:

1. Skip the current character.
2. Use the current character to match the next character of t, if they are equal.

The recursion tracks:

• The current index in s.
• The current index in t.

When all characters of t have been matched, one valid subsequence has been found. If s is exhausted before t, that branch contributes zero.

Naive Pseudocode

count(i, j):
    if j == length(t):
        return 1

    if i == length(s):
        return 0

    ways = count(i + 1, j)  // Skip s[i]

    if s[i] == t[j]:
        ways += count(i + 1, j + 1)  // Use s[i]

    return ways

The recursion can branch into two paths for many positions of s. In the worst case, it explores an exponential number of choices.

Complexity

• Time: O(2^m), where m = s.length
• Space: O(m) for the recursion stack

With s.length and t.length up to 1000, exponential recursion quickly becomes infeasible and results in Time Limit Exceeded. Many recursive calls also solve the same (i, j) state repeatedly.

Algorithm Strategy: Dynamic Programming (DP Patterns)

Maintain a one-dimensional array:

dp[j] = number of ways to form the first j characters of t
        using the characters of s processed so far

Initialize:

dp[0] = 1

This represents the one valid way to form an empty target: select no indices.

For every character c in s:

1. Traverse t from its last character toward its first.
2. If c matches t[j - 1], add dp[j - 1] to dp[j].
3. If the characters do not match, leave dp[j] unchanged.

The right-to-left traversal enforces the prefix-state boundary: dp[j - 1] must refer to the state before processing the current character of s.

After all characters of s are processed, dp[t.length()] contains the number of distinct index selections that form t.

Execution Flow

1. Create an array of length t.length() + 1.
2. Set dp[0] = 1.
3. Process each character of s from left to right.
4. For the current source character, process target lengths from t.length() down to 1.
5. Compare the source character with t[j - 1].
6. If they match:
   • dp[j - 1] counts ways to form the shorter target prefix before using the current source character.
   • Add that count to dp[j].
7. If they do not match, no new subsequence ending at this source character is created.
8. Continue until every character of s has been processed.
9. Return dp[t.length()].

For s = "abac" and t = "ac":

• The first a creates one way to form "a".
• The b changes nothing.
• The second a creates another way to form "a".
• The final c extends both existing "a" formations into "ac".

The final count is 2.

Proof of Correctness

We prove that the algorithm returns the number of distinct subsequences of s equal to t.

Invariant

After processing a prefix of s, dp[j] equals the number of ways to select indices from that processed prefix so that the selected characters form t[:j].

Initialization

Before processing any characters of s:

• dp[0] = 1, because the empty target can be formed by selecting no characters.
• Every dp[j] for j > 0 is 0, because a nonempty target cannot be formed from an empty source prefix.

Thus, the invariant holds initially.

Maintenance

Consider processing a source character c.

For a target prefix of length j:

• If c != t[j - 1], the current character cannot be the final selected character of t[:j]. All valid selections remain the selections counted before processing c, so dp[j] remains unchanged.
• If c == t[j - 1], every existing way to form t[:j-1] can either:
  • Avoid c, already counted in the old dp[j].
  • Use c as the final character, contributing the old dp[j-1].

Therefore:

new dp[j] = old dp[j] + old dp[j - 1]

Because j is processed from right to left, dp[j - 1] still contains the value from before processing c. Thus, the update exactly represents the two valid choices without reusing c more than once.

The invariant is preserved after every source character.

Termination

After all characters of s are processed, dp[t.length()] counts every index selection whose characters spell the complete target t. Therefore, the algorithm returns the correct answer.

Pattern Reuse Notes

The following problems share the same pattern/subpattern:

• LeetCode 1143: Longest Common Subsequence
• LeetCode 1092: Shortest Common Supersequence
• LeetCode 1312: Minimum Insertion Steps to Make a String Palindrome

These problems define states over two string prefixes and transition based on whether the current characters match. The stored value changes by problem: counting ways for Distinct Subsequences, maximizing length for LCS, minimizing construction length for Shortest Common Supersequence, and minimizing insertions for the palindrome problem.

Reference Implementation

C++ Solution for LeetCode 115

1class Solution {
2public:
3    int numDistinct(string s, string t) {
4        vector<long long> dp(t.size() + 1, 0);
5        dp[0] = 1;
6
7        for (char c : s) {
8            for (size_t j = t.size(); j > 0; --j) {
9                if (c == t[j - 1]) {
10                    dp[j] += dp[j - 1];
11                }
12            }
13        }
14
15        return static_cast<int>(dp[t.size()]);
16    }
17};

Java Solution for LeetCode 115

1class Solution {
2    public int numDistinct(String s, String t) {
3        int[] dp = new int[t.length() + 1];
4        dp[0] = 1;
5
6        for (int i = 0; i < s.length(); i++) {
7            char ch = s.charAt(i);
8            for (int j = t.length(); j >= 1; j--) {
9                if (ch == t.charAt(j - 1)) {
10                    dp[j] += dp[j - 1];
11                }
12            }
13        }
14
15        return dp[t.length()];
16    }
17}

Python Solution for LeetCode 115

1class Solution:
2    def numDistinct(self, s: str, t: str) -> int:
3        # dp[j] is the number of ways to form t[:j] from the processed part of s.
4        dp = [0] * (len(t) + 1)
5        dp[0] = 1
6
7        for ch in s:
8            for j in range(len(t), 0, -1):
9                if ch == t[j - 1]:
10                    dp[j] += dp[j - 1]
11
12        return dp[len(t)]