Loading problem...
You are given two strings: a source string s and a pattern string t. Your task is to determine how many unique ways you can form the string t by selecting characters from s in order, without rearranging them.
A subsequence of a string is a new string formed by deleting zero or more characters from the original string while preserving the relative order of the remaining characters. For example, "ace" is a subsequence of "abcde", but "aec" is not (the order is not preserved).
Two subsequences are considered different if they are extracted from different positions in the source string, even if the resulting characters are the same. Your goal is to count all such distinct extraction patterns that yield the pattern string t.
The result is guaranteed to fit within a 32-bit signed integer.
s = "rabbbit"
t = "rabbit"3There are exactly 3 unique ways to extract "rabbit" from "rabbbit": • Select indices [0,1,2,3,5,6] → "rabb" + "it" (using first three b's, skip fourth b) • Select indices [0,1,2,4,5,6] → "rab" + "bit" (using first two b's, skip third, use fourth) • Select indices [0,1,3,4,5,6] → "ra" + "bbit" (using first b, skip second, use third and fourth) Each extraction follows a different path through the source string, producing the same target.
s = "babgbag"
t = "bag"5There are 5 unique ways to form "bag" from "babgbag": • Indices [0,1,3]: "b"(0) + "a"(1) + "g"(3) • Indices [0,1,6]: "b"(0) + "a"(1) + "g"(6) • Indices [0,5,6]: "b"(0) + "a"(5) + "g"(6) • Indices [2,5,6]: "b"(2) + "a"(5) + "g"(6) • Indices [4,5,6]: "b"(4) + "a"(5) + "g"(6)
s = "aaa"
t = "a"3Each of the three 'a' characters can independently form the pattern "a", giving us 3 unique subsequences.
Constraints