Distinct Subsequences

Hard · 2-D Dynamic Programming

You are given two strings, s and t. Count how many distinct ways you can select a subsequence of s (choosing characters in order, but not necessarily contiguous) so that it exactly equals t. Return that count. Two selections count as different if they use different index positions from s, even if the picked characters look identical.

Examples

Input:  s = "rabbbit", t = "rabbit"
Output: 3
Why:    There are 3 different ways to remove one 'b' from s to spell out t.

Input:  s = "babgbag", t = "bag"
Output: 5
Why:    There are 5 different ways to pick letters from s in order that spell 'bag'.

Input:  s = "abc", t = "abcd"
Output: 0
Why:    t is longer in required letters than what s can supply in order, so no way exists.

Constraints

0 <= s.length, t.length <= 1000, s and t consist of English letters only, the answer fits in a 32-bit signed integer

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Distinct Subsequences

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Distinct Subsequences. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.