Distinct Subsequences - Practice Coding Problems

Distinct Subsequences - Problem

Given two strings s and t, return the number of distinct subsequences of s which equals t.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ACE" is a subsequence of "ABCDE" while "AEC" is not).

The test cases are generated so that the answer fits on a 32-bit signed integer.

Input & Output

Example 1 — Basic Case

$ Input: s = "rabbbit", t = "rabbit"

› Output: 3

💡 Note: There are 3 ways to form "rabbit" from "rabbbit": r-a-b-b-b-i-t (skip 1st b), r-a-b-b-b-i-t (skip 2nd b), r-a-b-b-b-i-t (skip 3rd b)

Example 2 — No Match

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

› Output: 5

💡 Note: Five ways to form "bag": b-a-g(1st), b-a-g(2nd), b-a-g(3rd), b-a-g(4th), b-a-g(5th) using different combinations of b, a, g characters

Example 3 — Edge Case

$ Input: s = "abc", t = "def"

› Output: 0

💡 Note: No characters match between s and t, so no subsequences of s can form t

Constraints

1 ≤ s.length, t.length ≤ 1000
s and t consist of English letters only

Visualization

Tap to expand

Understanding the Visualization

Input

Source string s and target string t

Process

Count all ways to pick characters from s (in order) to form t

Output

Total number of distinct subsequences

Key Takeaway

🎯 Key Insight: When characters match, we can choose to include or skip them, creating a tree of possibilities that DP efficiently counts

Asked in

G Google 25 a Amazon 18 F Facebook 15 M Microsoft 12

The key insight is recognizing this as a classic DP problem where we count ways to match subsequences. When characters match, we can either include or exclude them, leading to overlapping subproblems. Best approach is 2D Dynamic Programming with optional space optimization. Time: O(n×m), Space: O(m) optimized.

Common Approaches

Approach	Time	Space	Notes
✓ Top-Down with Memoization	O(n×m)	O(n×m)	Recursive solution with caching to avoid recomputation
2D Dynamic Programming	O(n×m)	O(n×m)	Bottom-up DP table to count distinct subsequences
Recursive Brute Force	O(2^n)	O(n)	Try all possible subsequences using recursion
Space-Optimized DP	O(n×m)	O(m)	1D DP array using only previous row information

Top-Down with Memoization — Algorithm Steps

Use recursion with two pointers (i for s, j for t)
Cache results in a 2D memo table
Return cached result if subproblem already solved

Visualization

Tap to expand

Step-by-Step Walkthrough

First Call

Calculate and cache dp(i,j) result

Cache Hit

Return cached result for repeated (i,j) state

Efficiency

Each state computed only once

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int memo[1001][51];
int visited[1001][51];

int dp(const char* s, const char* t, int i, int j, int sLen, int tLen) {
    if (j == tLen) return 1;
    if (i == sLen) return 0;
    
    if (visited[i][j]) {
        return memo[i][j];
    }
    
    int count = 0;
    if (s[i] == t[j]) {
        count += dp(s, t, i + 1, j + 1, sLen, tLen);
    }
    count += dp(s, t, i + 1, j, sLen, tLen);
    
    memo[i][j] = count;
    visited[i][j] = 1;
    return count;
}

int solution(char* s, char* t) {
    memset(visited, 0, sizeof(visited));
    return dp(s, t, 0, 0, strlen(s), strlen(t));
}

int main() {
    char s[1001], t[51];
    fgets(s, sizeof(s), stdin);
    fgets(t, sizeof(t), stdin);
    s[strcspn(s, "\n")] = 0;
    t[strcspn(t, "\n")] = 0;
    int result = solution(s, t);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n×m)

Each of the n×m states is computed once and cached

✓ Linear Growth

Space Complexity

O(n×m)

Memoization table stores results for all (i,j) combinations plus recursion stack

⚡ Linearithmic Space

78.0K Views

Medium Frequency

~25 min Avg. Time

2.1K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Top-Down with Memoization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler