Given two strings, s and t, determine how many distinct subsequences of s match t exactly.
Note: A subsequence is formed by deleting zero or more characters from s without changing the relative order of the remaining characters.
You may assume the result will always fit within a
Constraints:
s.length, t.length
s and t consist of English letters.
The problem asks for the number of distinct subsequences of string s that exactly match string t. A subsequence allows skipping characters but must preserve order.
A key observation is that this problem naturally fits a dynamic programming structure:
For every position i in s and every position j in t, we want to know:
How many subsequences of
s[i:]matcht[j:]?
If characters match (s[i] == t[j]), then we have two choices:
Use this matching pair and count subsequences of the remainder (t[j+1:]).
Skip the character in s and continue searching.
If characters don’t ...
Given two strings, s and t, determine how many distinct subsequences of s match t exactly.
Note: A subsequence is formed by deleting zero or more characters from s without changing the relative order of the remaining characters.
You may assume the result will always fit within a
Constraints:
s.length, t.length
s and t consist of English letters.
The problem asks for the number of distinct subsequences of string s that exactly match string t. A subsequence allows skipping characters but must preserve order.
A key observation is that this problem naturally fits a dynamic programming structure:
For every position i in s and every position j in t, we want to know:
How many subsequences of
s[i:]matcht[j:]?
If characters match (s[i] == t[j]), then we have two choices:
Use this matching pair and count subsequences of the remainder (t[j+1:]).
Skip the character in s and continue searching.
If characters don’t ...