hardDynamic Programming 2DAI-applied~40 min
Count Matching Template Subsequences
A guardrail scans a model's output stream s for how many distinct ways a banned template t can be formed as a subsequence (preserving order, skipping freely). The count drives a risk score.
Problem
Given strings s and t, return the number of distinct subsequences of s that equal t. A subsequence keeps relative order but may skip characters. The answer fits in a 32-bit signed integer.
Input
Two strings s and t (0 ≤ |t| ≤ |s| ≤ 1000), consisting of letters.
Output
An integer count of subsequences of s equal to t.
Constraints
- 0 ≤ |t| ≤ |s| ≤ 1000
- The answer fits in a signed 32-bit integer
- Matching is case-sensitive
Examples
Example 1
Input
s = "rabbbit", t = "rabbit"
Output
3
Three distinct choices of which 'b's to keep form 'rabbit'.
Example 2
Input
s = "babgbag", t = "bag"
Output
5
Five distinct index sets spell 'bag'.