#0304

Distinct Subsequences

HardDSA40 min25 XP

Problem

Given s and t, return how many distinct subsequences of s equal t.

Why This Matters

This is a powerful DP pattern for counting choices rather than merely checking existence.

Function Signature

def num_distinct(s, t):

Examples

Example 1

Inputs = "rabbbit", t = "rabbit"

Output3

There are three ways to delete one of the three b characters.

Constraints

Return the exact requested value.
Handle edge cases cleanly.
Use the intended DSA pattern when brute force would scale poorly.

CodePython

def num_distinct(s, t):
    """
    Input example: s = "rabbbit", t = "rabbit"
    Return: 3
    Return the value from the function so the tests can compare it. Do not print unless the prompt asks.
    """
    # write your code here
    return 0

def num_distinct(s, t):
    """
    Input example: s = "rabbbit", t = "rabbit"
    Return: 3
    Return the value from the function so the tests can compare it. Do not print unless the prompt asks.
    """
    # write your code here
    return 0

Visible browser tests run here when available.

Testcases2 visible / 3 hidden categories

Three rabbits

Inputrabbbit -> rabbit

Expected3

Choose which extra b to skip.

Five bags

Inputbabgbag -> bag

Expected5

There are five index choices that spell bag.

Hidden Test Categories

empty targettarget longer than sourceno matching characters