Skip to content
BASA DSA

Distinct Subsequences

Hard2-D Dynamic Programming

Count subsequences of s whose characters spell t, counting distinct selected index sets separately.

Example 1

Input
s = "babgbag"
t = "bag"
Output
5

Explanation

Index triples (0,1,3), (0,1,6), (0,5,6), (2,5,6), (4,5,6) spell bag, giving five.

Example 2

Input
s = "aaa"
t = "aa"
Output
3

Explanation

Choose any two of three a positions, giving three index sets.

Example 3

Input
s = "abc"
t = "d"
Output
0

Explanation

No d occurs in the source, so no matching subsequence exists.

Example 4

Input
s = "abc"
t = ""
Output
1

Explanation

The empty target has one subsequence: select no source positions.

Constraints

  • 0 <= len(s),len(t) <= 1000
  • Strings contain English letters
  • The answer fits a signed 32-bit integer

Function contractnumDistinctArguments: json, json
Loading draft…
SolutionRuns on your device