Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in C++

Solution: Distinct Subsequences

Explore how to use dynamic programming to count the number of distinct subsequences of one string that match another exactly. This lesson teaches a space-optimized 1D DP technique to solve the problem more efficiently, helping you understand recursion dependencies and iteration order for complex string matching tasks in coding interviews.

We'll cover the following...

Statement

Given two strings, s and t, determine how many distinct subsequences of s match t exactly.

Note: A subsequence is formed by deleting zero or more characters from s without changing the relative order of the remaining characters.

You may assume the result will always fit within a 3232-bit signed integer.

Constraints:

  • 1≤1 \leq s.length, t.length ≤1000\leq 1000 ...