Distinct Subsequences
Distinct Subsequences is a hard dynamic programming problem solved with the strings pattern.
The best approach, optimal (one row, updated left to right), runs in O(n · m) time and O(m) space.
Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (skip or use each character) up.
Problem
Given two strings s and t, count in how many different ways t can be obtained as a subsequence of s.
A subsequence keeps some characters of s in their original order and drops the rest. Two ways are different when they use a different set of positions in s, even if they spell the same thing.
Examples
Example 1
- Input
s = "abbccc", t = "bc"- Output
6- Why
- Either b (positions 1 or 2) can be paired with any of the three c's (positions 3, 4, 5): 2 × 3 = 6 ways.
Example 2
- Input
s = "abcabc", t = "abc"- Output
4- Why
- Pick positions (0,1,2), (0,1,5), (0,4,5) or (3,4,5): four different index choices spell "abc".
Example 3
- Input
s = "xyz", t = "zz"- Output
0- Why
- s has only one z, so "zz" cannot be formed.
Constraints
1 <= s.length, t.length <= 1000sandtconsist of lowercase English letters.- The answer fits in a 32-bit signed integer.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (skip or use each character) | O(2^n) | O(n) |
| Better (2D table) | O(n · m) | O(n · m) |
| Optimal (one row, updated left to right) | O(n · m) | O(m) |
1Brute force (skip or use each character)
O(2^n)Each character of s may branch into two calls.O(n)The recursion depth is at most n.Recursively decide for each character of s whether to skip it or, when it matches the next needed character of t, use it. Count every way that matches all of t. The same (i, j) states are recomputed many times.
- count(i, j): if j == t.length, return 1 (all of t matched).
- If the characters left in s are fewer than those left in t, return 0.
- ways = count(i + 1, j); if s[i] == t[j], add count(i + 1, j + 1).
- Return count(0, 0).
class Solution {
public int numDistinct(String s, String t) {
return count(s, t, 0, 0);
}
private int count(String s, String t, int i, int j) {
if (j == t.length()) return 1;
if (s.length() - i < t.length() - j) return 0;
int ways = count(s, t, i + 1, j);
if (s.charAt(i) == t.charAt(j)) ways += count(s, t, i + 1, j + 1);
return ways;
}
}class Solution:
def numDistinct(self, s: str, t: str) -> int:
n, m = len(s), len(t)
def count(i: int, j: int) -> int:
if j == m:
return 1
if n - i < m - j:
return 0
ways = count(i + 1, j)
if s[i] == t[j]:
ways += count(i + 1, j + 1)
return ways
return count(0, 0)class Solution {
int count(const string& s, const string& t, int i, int j) {
if (j == (int)t.size()) return 1;
if ((int)s.size() - i < (int)t.size() - j) return 0;
int ways = count(s, t, i + 1, j);
if (s[i] == t[j]) ways += count(s, t, i + 1, j + 1);
return ways;
}
public:
int numDistinct(string s, string t) {
return count(s, t, 0, 0);
}
};function numDistinct(s, t) {
const n = s.length, m = t.length;
const count = (i, j) => {
if (j === m) return 1;
if (n - i < m - j) return 0;
let ways = count(i + 1, j);
if (s[i] === t[j]) ways += count(i + 1, j + 1);
return ways;
};
return count(0, 0);
}2Better (2D table)
O(n · m)Each of the n · m cells is filled once in O(1).O(n · m)The full table is stored.Turn the recursion into a table. dp[i][j] is the number of ways to form t[j..] from s[i..]. Fill it from the bottom-right corner so every value it depends on is already known.
- Create dp of size (n + 1) x (m + 1); set dp[i][m] = 1 for every i (empty rest of t).
- For i from n - 1 down to 0 and j from m - 1 down to 0: dp[i][j] = dp[i+1][j], plus dp[i+1][j+1] when s[i] == t[j].
- Return dp[0][0].
class Solution {
public int numDistinct(String s, String t) {
int n = s.length(), m = t.length();
int[][] dp = new int[n + 1][m + 1];
for (int i = 0; i <= n; i++) dp[i][m] = 1;
for (int i = n - 1; i >= 0; i--) {
for (int j = m - 1; j >= 0; j--) {
dp[i][j] = dp[i + 1][j];
if (s.charAt(i) == t.charAt(j)) dp[i][j] += dp[i + 1][j + 1];
}
}
return dp[0][0];
}
}class Solution:
def numDistinct(self, s: str, t: str) -> int:
n, m = len(s), len(t)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1):
dp[i][m] = 1
for i in range(n - 1, -1, -1):
for j in range(m - 1, -1, -1):
dp[i][j] = dp[i + 1][j]
if s[i] == t[j]:
dp[i][j] = (dp[i][j] + dp[i + 1][j + 1]) & 0xFFFFFFFF
return dp[0][0]class Solution {
public:
int numDistinct(string s, string t) {
int n = s.size(), m = t.size();
vector<vector<unsigned int>> dp(n + 1, vector<unsigned int>(m + 1, 0));
for (int i = 0; i <= n; i++) dp[i][m] = 1;
for (int i = n - 1; i >= 0; i--) {
for (int j = m - 1; j >= 0; j--) {
dp[i][j] = dp[i + 1][j];
if (s[i] == t[j]) dp[i][j] += dp[i + 1][j + 1];
}
}
return (int)dp[0][0];
}
};function numDistinct(s, t) {
const n = s.length, m = t.length;
const dp = Array.from({ length: n + 1 }, () => new Array(m + 1).fill(0));
for (let i = 0; i <= n; i++) dp[i][m] = 1;
for (let i = n - 1; i >= 0; i--) {
for (let j = m - 1; j >= 0; j--) {
dp[i][j] = dp[i + 1][j];
if (s[i] === t[j]) dp[i][j] = (dp[i][j] + dp[i + 1][j + 1]) | 0;
}
}
return dp[0][0];
}3Optimal (one row, updated left to right)
O(n · m)Still one O(1) update per (i, j) pair.O(m)Only one array of length m + 1.Row i of the table only reads row i + 1, so one array dp over j is enough. When processing s[i], updating dp[j] needs the old dp[j+1]; walking j from left to right reads dp[j+1] before it is changed in this round. Counts for short pieces of t can grow far beyond 32 bits even when the final answer fits; letting them wrap around (plain int arithmetic) is safe, because addition modulo 2^32 still yields the right final value.
- Create dp of length m + 1 with dp[m] = 1 and the rest 0.
- For i from n - 1 down to 0, for j from 0 to m - 1: if s[i] == t[j], dp[j] += dp[j+1].
- Return dp[0].
class Solution {
public int numDistinct(String s, String t) {
int n = s.length(), m = t.length();
int[] dp = new int[m + 1];
dp[m] = 1;
for (int i = n - 1; i >= 0; i--) {
char c = s.charAt(i);
for (int j = 0; j < m; j++) {
if (c == t.charAt(j)) dp[j] += dp[j + 1];
}
}
return dp[0];
}
}class Solution:
def numDistinct(self, s: str, t: str) -> int:
m = len(t)
dp = [0] * (m + 1)
dp[m] = 1
for c in reversed(s):
for j in range(m):
if c == t[j]:
dp[j] = (dp[j] + dp[j + 1]) & 0xFFFFFFFF # keep 32 bits, like Java int
return dp[0]class Solution {
public:
int numDistinct(string s, string t) {
int n = s.size(), m = t.size();
vector<unsigned int> dp(m + 1, 0); // wraps like Java int
dp[m] = 1;
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j < m; j++) {
if (s[i] == t[j]) dp[j] += dp[j + 1];
}
}
return (int)dp[0];
}
};function numDistinct(s, t) {
const n = s.length, m = t.length;
const dp = new Array(m + 1).fill(0);
dp[m] = 1;
for (let i = n - 1; i >= 0; i--) {
for (let j = 0; j < m; j++) {
if (s[i] === t[j]) dp[j] = (dp[j] + dp[j + 1]) | 0; // 32-bit wrap
}
}
return dp[0];
}Edge cases to test
tlonger thans: answer 0sequalst: answer 1tuses a letter thatsdoes not contain: answer 0- Many repeated letters, like s = "aaaa" and t = "aa" (answer 6 = C(4, 2))
Hints
Hint 1
Look at the first character of s. Either you skip it, or, if it equals the first character of t, you use it to match that character.
Hint 2
Let dp[i][j] be the number of ways to form t[j..] from s[i..]. Then dp[i][j] = dp[i+1][j] + (s[i] == t[j] ? dp[i+1][j+1] : 0), and dp[i][m] = 1.
Hint 3
Row i only depends on row i + 1. Keep one array over j and update it from left to right so each value is read before it is overwritten.
FAQ
What is the best time complexity for Distinct Subsequences?
Optimal (one row, updated left to right) runs in O(n · m) time and O(m) extra space. Still one O(1) update per (i, j) pair.
Which pattern does Distinct Subsequences use?
It is a dynamic programming problem that uses the strings pattern. Other problems with the same pattern: Edit Distance, Longest Common Subsequence, Longest Palindromic Subsequence.
Is there a brute force solution for Distinct Subsequences?
Yes. Brute force (skip or use each character) takes O(2^n) time and O(n) space. Recursively decide for each character of s whether to skip it or, when it matches the next needed character of t, use it.
Which edge cases should I test for Distinct Subsequences?
t longer than s: answer 0; s equals t: answer 1; t uses a letter that s does not contain: answer 0; Many repeated letters, like s = "aaaa" and t = "aa" (answer 6 = C(4, 2)).