Count how many distinct subsequences of one string equal another target string.
Given two strings s and t, count how many distinct subsequences of s are exactly equal to t.
A subsequence is formed by deleting zero or more characters from a string without changing the relative order of the remaining characters. Different deletion choices that produce the same resulting characters are still counted separately if they come from different indices.
Your task is to return the number of distinct ways to form t from s as a subsequence.
Input Format
- Two strings
sandt. sis the source string.tis the target string to match as a subsequence.
Output Format
- Return an integer representing the number of distinct subsequences of
sequal tot.
Constraints
- The answer may be large; use a numeric type that can store the result.
- If
tis longer thans, the answer is0. - An empty target string can always be formed in exactly one way.
- A concise interview setting usually assumes lowercase or ASCII strings, but the core logic works for general strings.
Example 1
Input
s = "rabbbit", t = "rabbit"
Output
3
Explanation
There are 3 distinct ways to delete one of the three 'b' characters so that the remaining characters form rabbit.
Example 2
Input
s = "babgbag", t = "bag"
Output
5
Explanation
There are 5 different subsequences of s that spell bag.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.