115. Distinct Subsequences Solution - DP

The problem

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.

Approach overview

Problem Overview: Given two strings s and t, count how many distinct subsequences of s equal t. A subsequence keeps character order but can skip characters. The challenge is avoiding exponential exploration while counting all valid combinations.

Approach 1: Dynamic Programming 2D Table (O(m * n) time, O(m * n) space)

This approach builds a 2D DP table where dp[i][j] represents the number of ways the first i characters of s can form the first j characters of t. Initialize dp[i][0] = 1 because an empty string t can always be formed by deleting characters from s. Then iterate through both strings. If s[i-1] == t[j-1], add two possibilities: use the character (dp[i-1][j-1]) or skip it (dp[i-1][j]). If they differ, only skip the character in s (dp[i-1][j]). This method explicitly models all prefix combinations, making it easy to reason about and debug. Time complexity is O(m * n) and space complexity is also O(m * n).

This is a classic example of dynamic programming applied to a string matching problem where overlapping subproblems appear when multiple subsequences reuse the same prefixes.

Approach 2: Dynamic Programming with Space Optimization (O(m * n) time, O(n) space)

The full DP table stores many intermediate states that are only used once. Each row depends only on the previous row, so you can compress the table into a single 1D array. Maintain dp[j] as the number of ways to build the first j characters of t. Iterate through s, and update dp from right to left so previous states are not overwritten too early. When s[i-1] == t[j-1], update dp[j] += dp[j-1]. Right-to-left iteration preserves the values from the previous iteration of s. This reduces memory usage significantly while keeping the same O(m * n) runtime.

This optimization matters when the input strings are large, since the DP table can otherwise consume substantial memory. The algorithmic idea remains identical—count subsequence combinations using prefix relationships—but the storage is compressed to a single dimension.

Recommended for interviews: Interviewers usually expect the dynamic programming formulation first because it demonstrates understanding of subsequence counting and state transitions. Start by explaining the 2D DP definition (dp[i][j] meaning prefixes of s and t). Once the recurrence is clear, mention the 1D optimization to reduce space from O(m * n) to O(n). Showing both versions proves you understand both correctness and practical optimization.

Approach 1: Dynamic Programming 2D Table

We use a 2D DP table where `dp[i][j]` represents the number of distinct subsequences of `s[0..i-1]` which forms `t[0..j-1]`. The size of the table is `(m+1)x(n+1)` where `m` is the length of `s` and `n` is the length of `t`.

Initialize `dp[0][0]` to 1 because an empty string is a subsequence of itself, and `dp[i][0]` to 1 for all `i`, because an empty `t` is a subsequence of any prefix of `s`. Then, for each character `s[i-1]` and `t[j-1]`, update the DP table as follows:

If `s[i-1] == t[j-1]`, then `dp[i][j] = dp[i-1][j-1] + dp[i-1][j]`.
If `s[i-1] != t[j-1]`, then `dp[i][j] = dp[i-1][j]`.

Python

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):
            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]

# Example usage
print(numDistinct("rabbbit", "rabbit"))

Java

class Solution {
    public int numDistinct(String s, String t) {
        int m = s.length();
        int 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++) {
                if (s.charAt(i - 1) == t.charAt(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];
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.numDistinct("rabbbit", "rabbit"));
    }
}

C++

#include <vector>
#include <string>

int numDistinct(std::string s, std::string t) {
    int m = s.size();
    int n = t.size();
    std::vector<std::vector<long long>> dp(m + 1, std::vector<long long>(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) {
            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];
}

int main() {
    std::string s = "rabbbit";
    std::string t = "rabbit";
    std::cout << numDistinct(s, t) << std::endl;
    return 0;
}

JavaScript

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++) {
            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];
}

// Example usage
console.log(numDistinct("rabbbit", "rabbit"));

#include <stdio.h>
#include <string.h>

int numDistinct(char* s, char* t) {
    int m = strlen(s);
    int n = strlen(t);
    int dp[m + 1][n + 1];
    
    for (int i = 0; i <= m; i++) {
        dp[i][0] = 1;
    }
    for (int j = 1; j <= n; j++) {
        dp[0][j] = 0;
    }
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            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];
}

int main() {
    char s[] = "rabbbit";
    char t[] = "rabbit";
    printf("%d\n", numDistinct(s, t));
    return 0;
}

using System;

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++) {
                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];
    }

    public static void Main(string[] args) {
        Solution sol = new Solution();
        Console.WriteLine(sol.NumDistinct("rabbbit", "rabbit"));
    }
}

This Python solution uses a nested list `dp` to store the number of subsequences. The outer loop iterates over each character in `s`, while the inner loop checks each character of `t`, updating the DP table based on whether characters match or not. The result can be found at the last element `dp[m][n]`.

Complexity

Time Complexity: O(m * n)
Space Complexity: O(m * n)

Try this approach in the editor

Approach 2: Dynamic Programming with Space Optimization

We can optimize the space complexity by observing that to calculate `dp[i][j]`, we only need values from the previous row. Thus, we can use a 2-row approach, maintaining only `previous` and `current` arrays to save space. This reduces the space complexity to O(n), where `n` is the length of `t`.

The transition is similar to the 2D approach but only updates the necessary parts of the `current` array based on the `previous` row.

Python

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

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

# Example usage
print(numDistinct("rabbbit", "rabbit"))

Java

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

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                cur[j] = s.charAt(i - 1) == t.charAt(j - 1) ? prev[j - 1] + prev[j] : prev[j];
            }
            System.arraycopy(cur, 0, prev, 0, n + 1);
        }
        return prev[n];
    }

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

C++

#include <vector>
#include <string>

int numDistinct(std::string s, std::string t) {
    int m = s.size(), n = t.size();
    std::vector<long long> prev(n + 1, 0), cur(n + 1, 0);
    prev[0] = cur[0] = 1;

    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            cur[j] = s[i - 1] == t[j - 1] ? prev[j - 1] + prev[j] : prev[j];
        }
        prev = cur;
    }
    return prev[n];
}

int main() {
    std::string s = "rabbbit";
    std::string t = "rabbit";
    std::cout << numDistinct(s, t) << std::endl;
    return 0;
}

JavaScript

function numDistinct(s, t) {
    const m = s.length, n = t.length;
    const prev = Array(n + 1).fill(0);
    const cur = Array(n + 1).fill(0);

    prev[0] = cur[0] = 1;

    for (let i = 1; i <= m; ++i) {
        for (let j = 1; j <= n; ++j) {
            cur[j] = s[i - 1] === t[j - 1] ? prev[j - 1] + prev[j] : prev[j];
        }
        [prev, cur] = [cur, prev];
    }

    return prev[n];
}

// Example usage
console.log(numDistinct("rabbbit", "rabbit"));

#include <stdio.h>
#include <string.h>

int numDistinct(char* s, char* t) {
    int m = strlen(s);
    int n = strlen(t);
    int dp[2][n + 1];
    memset(dp, 0, sizeof(dp));
    dp[0][0] = dp[1][0] = 1;

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

int main() {
    char s[] = "rabbbit";
    char t[] = "rabbit";
    printf("%d\n", numDistinct(s, t));
    return 0;
}

using System;

public class Solution {
    public int NumDistinct(string s, string t) {
        int m = s.Length, n = t.Length;
        int[] prev = new int[n + 1];
        int[] cur = new int[n + 1];
        prev[0] = cur[0] = 1;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (s[i] == t[j]) {
                    cur[j + 1] = prev[j] + prev[j + 1];
                } else {
                    cur[j + 1] = prev[j + 1];
                }
            }
            Array.Copy(cur, prev, n + 1);
        }

        return prev[n];
    }

    public static void Main(string[] args) {
        Solution sol = new Solution();
        Console.WriteLine(sol.NumDistinct("rabbbit", "rabbit"));
    }
}

The Python solution maintains two lists, `prev` and `cur`. The current result is calculated from the previous row (list), and `prev` is updated to `cur` after calculating each row.

Complexity

Time Complexity: O(m * n)
Space Complexity: O(n)

Try this approach in the editor

Approach 3: Dynamic Programming

We define f[i][j] as the number of schemes where the first i characters of string s form the first j characters of string t. Initially, f[i][0]=1 for all i \in [0,m].

When i > 0, we consider the calculation of f[i][j]:

When s[i-1] \ne t[j-1], we cannot select s[i-1], so f[i][j]=f[i-1][j];
Otherwise, we can select s[i-1], so f[i][j]=f[i-1][j-1].

Therefore, we have the following state transition equation:

$f[i][j]=\left{ \begin{aligned} &f[i-1][j], &s[i-1] \ne t[j-1] \ &f[i-1][j-1]+f[i-1][j], &s[i-1]=t[j-1] \end{aligned} \right.

The final answer is f[m][n], where m and n are the lengths of strings s and t respectively.

The time complexity is O(m times n), and the space complexity is O(m times n).

We notice that the calculation of f[i][j] is only related to f[i-1][..]. Therefore, we can optimize the first dimension, reducing the space complexity to O(n)$.

TypeScript

function numDistinct(s: string, t: string): number {
    const m = s.length;
    const n = t.length;
    const f: number[][] = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
    for (let i = 0; i <= m; ++i) {
        f[i][0] = 1;
    }
    for (let i = 1; i <= m; ++i) {
        for (let j = 1; j <= n; ++j) {
            f[i][j] = f[i - 1][j];
            if (s[i - 1] === t[j - 1]) {
                f[i][j] += f[i - 1][j - 1];
            }
        }
    }
    return f[m][n];
}

func numDistinct(s string, t string) int {
	m, n := len(s), len(t)
	f := make([][]int, m+1)
	for i := range f {
		f[i] = make([]int, n+1)
	}
	for i := 0; i <= m; i++ {
		f[i][0] = 1
	}
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			f[i][j] = f[i-1][j]
			if s[i-1] == t[j-1] {
				f[i][j] += f[i-1][j-1]
			}
		}
	}
	return f[m][n]
}

Rust

impl Solution {
    #[allow(dead_code)]
    pub fn num_distinct(s: String, t: String) -> i32 {
        let n = s.len();
        let m = t.len();
        let mut dp: Vec<Vec<u64>> = vec![vec![0; m + 1]; n + 1];

        // Initialize the dp vector
        for i in 0..=n {
            dp[i][0] = 1;
        }

        // Begin the actual dp process
        for i in 1..=n {
            for j in 1..=m {
                dp[i][j] = if s.as_bytes()[i - 1] == t.as_bytes()[j - 1] {
                    dp[i - 1][j] + dp[i - 1][j - 1]
                } else {
                    dp[i - 1][j]
                };
            }
        }

        dp[n][m] as i32
    }
}

Try this approach in the editor

Approach 4: Default Approach

TypeScript

function numDistinct(s: string, t: string): number {
    const n = t.length;
    const f: number[] = new Array(n + 1).fill(0);
    f[0] = 1;
    for (const a of s) {
        for (let j = n; j; --j) {
            const b = t[j - 1];
            if (a === b) {
                f[j] += f[j - 1];
            }
        }
    }
    return f[n];
}

func numDistinct(s string, t string) int {
	n := len(t)
	f := make([]int, n+1)
	f[0] = 1
	for _, a := range s {
		for j := n; j > 0; j-- {
			if b := t[j-1]; byte(a) == b {
				f[j] += f[j-1]
			}
		}
	}
	return f[n]
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Dynamic Programming 2D Table	Time Complexity: O(m * n) Space Complexity: O(m * n)
Dynamic Programming with Space Optimization	Time Complexity: O(m * n) Space Complexity: O(n)
Dynamic Programming	–
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Dynamic Programming 2D Table	O(m * n)	O(m * n)	Best for understanding the recurrence and debugging state transitions
DP with Space Optimization (1D)	O(m * n)	O(n)	Preferred in interviews and large inputs where memory efficiency matters

Frequently asked questions

Is Distinct Subsequences easy or hard?

Distinct Subsequences is classified as a Hard problem because it requires recognizing a non-trivial dynamic programming state and handling combinatorial counting. The recurrence and space optimization often make it challenging for beginners.

Distinct Subsequences Python/Java solution

Most implementations follow the same DP recurrence across languages. Python and Java solutions typically use nested loops to fill a DP table or update a 1D array, resulting in O(m*n) runtime with optional O(n) space optimization.

How to solve Distinct Subsequences in O(n)?

The problem cannot be solved in pure O(n) time because every character of s must be compared against characters of t. However, the DP table can be compressed to O(n) space using a 1D array updated from right to left while iterating through s.

What is the best approach for Distinct Subsequences?

Dynamic programming is the standard solution. Define dp[i][j] as the number of ways the first i characters of s can form the first j characters of t. The transition either skips the current character in s or matches it with t when they are equal. This produces an O(m*n) time solution and can be optimized to O(n) space.

Is Distinct Subsequences asked at Google/Amazon/Meta?

Distinct subsequence counting problems appear frequently in interviews at large tech companies including Google, Amazon, and Meta. The question tests understanding of dynamic programming on strings, state transitions, and space optimization.

What data structure is used in Distinct Subsequences?

The core data structure is a dynamic programming array or table. The 2D version uses a matrix dp[m+1][n+1], while the optimized solution uses a single 1D array of size n+1 to store subsequence counts.

What is the time complexity of Distinct Subsequences?

The optimal dynamic programming solution runs in O(m*n) time, where m is the length of string s and n is the length of string t. Each pair of indices is processed once to compute the number of subsequence combinations.

Distinct Subsequences solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming 2D Table

Approach 2: Dynamic Programming with Space Optimization

Approach 3: Dynamic Programming

Approach 4: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Distinct Subsequences solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming 2D Table

Approach 2: Dynamic Programming with Space Optimization

Approach 3: Dynamic Programming

Approach 4: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems