Description
Count ways to delete characters from s so the remaining characters equal t. Different kept indices count separately. Assume the final answer fits a signed 32-bit integer.
Solution
def num_distinct(s, t):
ways = [0] * (len(t) + 1)
ways[0] = 1
for ch in s:
for j in range(len(t), 0, -1):
if ch == t[j - 1]:
ways[j] += ways[j - 1]
return ways[-1]Examples
Example 1
- Input
["rabbbit","rabbit"]- Output
3
Choose which two of the three b characters to retain.
Example 2
- Input
["babgbag","bag"]- Output
5
Five distinct index selections spell bag.
Example 3
- Input
["abc","abcd"]- Output
0
The source is shorter than the target.
Approach
Let ways[j] count matches of the first j target characters. Initialize the empty target to one. For each source character, update target positions from right to left; on a match add ways[j - 1] into ways[j]. Java and Go cap counts at the guaranteed answer limit to prevent irrelevant intermediate overflow.
Time & space
O(mn) time and O(n) auxiliary space under fixed-width counting, where m = len(s) and n = len(t). Python uses arbitrary-precision integers.