/115. Distinct Subsequences
Previous|Next

115. Distinct Subsequences

Hard
Strings51.6% acceptance

Given two strings source_string and target_string, return the number of distinct subsequences of source_string that are equal to target_string. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Example 1

Input: source_string=aaccc, target_string=ac

Output: 6

Explanation: There are 6 ways to form ac from aaccc.

Example 2

Input: source_string=xyzxyz, target_string=xyz

Output: 8

Explanation: There are 8 ways to form xyz from xyzxyz.

Constraints

  • 1 <= len(source_string) <= 1000
  • 1 <= len(target_string) <= 1000
  • source_string and target_string consist of English letters (a-z, A-Z)
Python (current runtime)

Case 1

Input: source_string='abcabc', target_string='abc'

Expected: 8

Case 2

Input: source_string='aaaa', target_string='aa'

Expected: 6

Case 3

Input: source_string='abcd', target_string='bd'

Expected: 1

Case 4

Input: source_string='zzzz', target_string='zzz'

Expected: 4

Case 5

Input: source_string='abcdef', target_string='ace'

Expected: 1