115. Distinct Subsequences

Hard

5.2K

198

Given two strings `s`

and `t`

, return *the number of distinct*

`s`

`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:3Explanation:As shown below, there are 3 ways you can generate "rabbit" from s.

brabbit

brabbit

brabbit

**Example 2:**

Input:s = "babgbag", t = "bag"Output:5Explanation:As shown below, there are 5 ways you can generate "bag" from s.

bbabagg

bgbabag

abgbbag`ba`

gbbag`babg`

bag

**Constraints:**

`1 <= s.length, t.length <= 1000`

`s`

and`t`

consist of English letters.

Accepted

285.7K

Submissions

642.7K

Acceptance Rate

44.4%

Seen this question in a real interview before?

1/4

Yes

No

Discussion (0)

Related Topics

Copyright ©️ 2023 LeetCode All rights reserved