Coding

Distinct subsequences

Asked at

Amazon

Microsoft

Swiggy

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given two strings s and t, return the number of distinct subsequences of s that equal t.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters. For example, "ace" is a subsequence of "abcde" while "aec" is not.

The task is to count how many different ways we can form t from s by deleting some (or no) characters from s. Return the result modulo 109+7.

Input: s = "axbxax", t = "axa"

Output: 2

Explanation: In the string "axbxax", there are two distinct subsequences "axa":

(a)(x)bx(a)x (a)xb(x)(a)x

Input: s = "babgbag", t = "bag"

Output: 5

Explanation: In the string "babgbag", there are five distinct subsequences "bag":

(ba)(b)(ga)(g) (ba)(bg)(ag) (bab)(ga)(g) (bab)(g)(ag) (babg)(a)(g)

Input: s = "abcde", t = "ace"

1 <= s.length, t.length <= 1000

cpp

class Solution{
  public: int distinctSubsequences(string s, string t){
	   
	}
};

java

class Solution {
    public int distinctSubsequences(String s, String t) {

    }
}

python

class Solution:
    def distinctSubsequences(self, s, t):

javascript

class Solution {
    distinctSubsequences(s, t) {
   
    }
}

csharp

public class Solution
{
    public int DistinctSubsequences(string s, string t)
    {

    }
}

func DistinctSubsequences(s string, t string) int {
   
}

Stuck? Show a way to structure it+

01Let dp[j] count ways to form the first j characters of t from the processed prefix of s.
02Initialize dp[0] to one for the empty target.
03For each source character, update matching target positions from right to left.
04Use the required numeric type or modulo for potentially large counts.

Reference answer

Use dp[j] for the number of ways the processed prefix of s can form the first j characters of t. There is exactly one way to form an empty target, so dp[0] = 1; other entries start at zero. For each character c in s, iterate j from t.length down to one. When c == t[j - 1], add dp[j - 1] to dp[j] modulo the required constant. The right-to-left order ensures the same source character is not reused multiple times during one iteration. The final answer is dp[t.length]. Time is O(|s| * |t|) and space is O(|t|). A two-dimensional DP expresses the same include-or-skip recurrence but uses O(|s| * |t|) space. If the target is longer than the source, the result naturally remains zero.

Then expect these follow-ups

What is the equivalent two-dimensional recurrence?
Tests: DP formulation
Why must the optimized update run right to left?
Tests: state dependency

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question