Distinct Subsequences

Hard

The problem

A subsequence keeps some characters of a string in order, possibly skipping some. Return how many different ways you can pick characters of s (by position) that spell t exactly.

Example 1
Input: s = "rabbbit", t = "rabbit"
Output: 3
You can skip any one of the three "b" characters in s.
Example 2
Input: s = "babgbag", t = "bag"
Output: 5
There are 5 different sets of positions in s that spell "bag".

Limits

1 ≤ len(s), len(t) ≤ 1,000
Both strings have only English letters
The answer fits in a 32-bit integer

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

When the characters match you may use the match or skip the character in s.

The idea

dp[i][j] = dp[i−1][j] (skip s[i−1]) + (s[i−1]==t[j−1] ? dp[i−1][j−1] : 0); dp[i][0] = 1.

Target: O(m·n) time

Go function shape

func numDistinct(s string, t string) int

Reference solution

Tested with go test. Try it yourself first, then compare.

// NumDistinct: how many ways does t appear as a subsequence of s?
// dp[j] = ways to build the first j letters of t from the part of s seen so far.
func NumDistinct(s, t string) int {
	dp := make([]int, len(t)+1)
	dp[0] = 1
	for i := 0; i < len(s); i++ {
		for j := len(t); j >= 1; j-- { // descending so dp[j-1] still holds the previous row
			if s[i] == t[j-1] {
				dp[j] += dp[j-1]
			}
		}
	}
	return dp[len(t)]
}

Read the lesson: 2-D Dynamic Programming