Distinct Subsequences

Distinct Subsequences is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Dynamic Programming (DP) Patterns pattern, in the 2D Array (Longest Common Subsequence - LCS) subpattern.

Problem statement

s and t are strings. A subsequence is formed by deleting zero or more characters while keeping every remaining character in its original relative order; the chosen characters do not need to be contiguous.

Count the different ways to choose indices from s whose characters, in increasing index order, spell t. Two choices are different when they use different indices, even if they produce the same sequence of characters.

Return the number of distinct subsequences of s equal to t. If t is empty, there is exactly one such subsequence: choose no characters. If s is empty while t is nonempty, return 0.

Example 1:

Input: s = "abac", t = "ac" Output: 2 Explanation: The target can use the a at index 0 or the a at index 2, followed by the c at index 3.

Example 2:

Input: s = "aaaaa", t = "aaa" Output: 10 Explanation: Any three of the five positions can be selected, giving 5 choose 3, or 10, index selections.

Example 3:

Input: s = "cabana", t = "can" Output: 2 Explanation: The c must be the first character and the n must be near the end; either of the first two usable a positions can be chosen between them.

Constraints:

- 1 <= s.length <= 1000 - 1 <= t.length <= 1000 - s and t contain only lowercase English letters - The answer fits in a 32-bit signed integer

Topics and companies

Topics: Dynamic Programming, String, Counting, Array.

How to practise Distinct Subsequences on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(|s| * |t|) time and O(|t|) space.

Open Distinct Subsequences in the code editor, or read the Distinct Subsequences editorial for a worked solution with its approach and complexity analysis.

Where Distinct Subsequences sits in the DSA pattern sheet

Problems related to Distinct Subsequences

Other problems that use the same 2D Array (Longest Common Subsequence - LCS) and Dynamic Programming (DP) Patterns techniques:

Preparing this workspace.