Counting Distinct Subsequences

This challenge focuses on finding the number of unique subsequences of a given string. Subsequences are fundamental to string manipulation and appear in various algorithmic problems, from pattern matching to bioinformatics. Mastering this concept will enhance your understanding of dynamic programming and combinatorial counting.

Problem Description

Given two strings, S and T, your task is to find the number of distinct subsequences of S that are equal to T.

A subsequence of a string is formed by deleting zero or more characters from the original string without changing the order of the remaining characters.

For instance, "ACE" is a subsequence of "ABCDE".

Key Requirements:

• You need to count distinct occurrences of T as a subsequence within S. This means if T can be formed from S in multiple ways using different character selections, each such way should be counted.
• The order of characters in T must be preserved when forming the subsequence from S.

Edge Cases to Consider:

• An empty string T.
• An empty string S.
• T being longer than S.
• S and T being identical.

Examples

Example 1:

Input:
S = "rabbbit"
T = "rabbit"
Output: 3
Explanation:
The distinct subsequences of "rabbbit" which equal "rabbit" are:
1. rabbbit
   ^^^^^^
2. rabbbit
   ^^ ^^^
3. rabbbit
   ^^^ ^^

Example 2:

Input:
S = "babgbag"
T = "bag"
Output: 5
Explanation:
The distinct subsequences of "babgbag" which equal "bag" are:
1. babgbag
   ^ ^ ^
2. babgbag
   ^ ^   ^
3. babgbag
   ^   ^ ^
4. babgbag
     ^ ^ ^
5. babgbag
       ^ ^ ^

Example 3:

Input:
S = "aaa"
T = "aa"
Output: 3
Explanation:
The distinct subsequences of "aaa" which equal "aa" are:
1. aaa
   ^^
2. aaa
   ^  ^
3. aaa
     ^^

Constraints

• The length of S will be between 0 and 1000, inclusive.
• The length of T will be between 0 and 1000, inclusive.
• Both S and T will consist only of English uppercase and lowercase letters.
• The result (number of distinct subsequences) will fit within a standard integer type.

Notes

This problem can be effectively solved using dynamic programming. Consider how the number of distinct subsequences for a prefix of S relates to the number of distinct subsequences for a shorter prefix. Pay close attention to the characters at the current positions in both S and T.