Given strings s and t, count the ways to choose increasing indices from s whose characters spell t. You may delete characters, but cannot reorder them. Different choices of source indices count separately, even when they produce the same text.

Return the count as a number. The final answer fits in a signed 32-bit integer; intermediate counts are not guaranteed to fit in that range.

Input: s = "banana", t = "ban"

Output: 3

Explanation: Using zero-based source indices, [0,1,2], [0,1,4], and [0,3,4] spell ban. The b at index 0 is fixed, but the chosen a must precede the chosen n. The final a cannot be used because no n follows it.

Input: s = "abc", t = "ca"

Output: 0

Explanation: The source abc contains both c and a, but c occurs after a. Deleting characters cannot reverse their order, so no subsequence spells ca.

Input: s = "aAaA", t = "AA"

Output: 1

Explanation: Matching is case-sensitive. Only the uppercase A positions 1 and 3 can form AA, giving one index choice.

217. Distinct Subsequences

Hard•

Return the count as a number. The final answer fits in a signed 32-bit integer; intermediate counts are not guaranteed to fit in that range.

Example 1:

Input: s = "banana", t = "ban"

Output: 3

Example 2:

Input: s = "abc", t = "ca"

Output: 0

Explanation: The source abc contains both c and a, but c occurs after a. Deleting characters cannot reverse their order, so no subsequence spells ca.

Example 3:

Input: s = "aAaA", t = "AA"

Output: 1

Explanation: Matching is case-sensitive. Only the uppercase A positions 1 and 3 can form AA, giving one index choice.

Constraints

1 <= s.length, t.length <= 1000
s and t contain uppercase or lowercase English letters.
The final answer is at most 2147483647.

Accepted4/4|Acceptance Rate100.0%

217. Distinct Subsequences

Constraints

Unlock Progressive Hints

217. Distinct Subsequences

Constraints

Unlock Progressive Hints