Distinct Subsequences II - Practice Coding Problems

Distinct Subsequences II - Problem

Given a string s, return the number of distinct non-empty subsequences of s. Since the answer may be very large, return it modulo 10^9 + 7.

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).

Input & Output

Example 1 — Basic Case

$ Input: s = "abc"

› Output: 7

💡 Note: The distinct subsequences are: "a", "b", "c", "ab", "ac", "bc", "abc". Total = 7.

Example 2 — Duplicate Characters

$ Input: s = "aba"

› Output: 4

💡 Note: The distinct subsequences are: "a", "b", "ab", "ba", "aba". Note that "a" appears twice in the string but is counted only once. Total = 4.

Example 3 — All Same Characters

$ Input: s = "aaa"

› Output: 3

💡 Note: The distinct subsequences are: "a", "aa", "aaa". All single 'a' subsequences are the same. Total = 3.

Constraints

1 ≤ s.length ≤ 2000
s consists of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input

String with possible duplicate characters

Process

Build subsequences while tracking character occurrences

Output

Count of distinct non-empty subsequences

Key Takeaway

🎯 Key Insight: Use DP to track character counts and subtract duplicates when the same character appears again

Asked in

a Amazon 25 G Google 18 M Microsoft 12

The key insight is to use dynamic programming to track subsequences ending with each character, avoiding duplicate counting. When we encounter a repeated character, we subtract the count from its previous occurrence. Best approach uses O(n) time and O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Generate All Subsequences	O(2^n * n)	O(2^n * n)	Generate all possible subsequences and count distinct ones using a set
Dynamic Programming with Character Tracking	O(n)	O(1)	Track the number of subsequences ending with each character to avoid duplicates

Generate All Subsequences — Algorithm Steps

Generate all 2^n subsequences using bit manipulation
Store each subsequence in a set to ensure uniqueness
Return the count of distinct subsequences

Visualization

Tap to expand

Step-by-Step Walkthrough

Input String

Process each character position

Generate Combinations

Use bitmask to include/exclude characters

Count Unique

Store in set and count distinct subsequences

Code -

solution.c — C

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

#define MAX_SUBSEQ 100000
#define MOD 1000000007

struct HashSet {
    char data[MAX_SUBSEQ][21];
    int size;
};

int contains(struct HashSet* set, char* str) {
    for (int i = 0; i < set->size; i++) {
        if (strcmp(set->data[i], str) == 0) {
            return 1;
        }
    }
    return 0;
}

void insert(struct HashSet* set, char* str) {
    if (!contains(set, str) && set->size < MAX_SUBSEQ) {
        strcpy(set->data[set->size], str);
        set->size++;
    }
}

int solution(char* s) {
    int n = strlen(s);
    struct HashSet subsequences = {.size = 0};
    
    // Generate all 2^n subsequences (limited for safety)
    int limit = (1 << n) > MAX_SUBSEQ ? MAX_SUBSEQ : (1 << n);
    for (int mask = 1; mask < limit; mask++) {
        char subseq[21] = {0};
        int idx = 0;
        for (int i = 0; i < n && i < 20; i++) {
            if (mask & (1 << i)) {
                subseq[idx++] = s[i];
            }
        }
        insert(&subsequences, subseq);
    }
    
    return subsequences.size % MOD;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(2^n * n)

Generate 2^n subsequences, each taking O(n) time to build

⚠ Quadratic Growth

Space Complexity

O(2^n * n)

Set stores up to 2^n subsequences, each of length up to n

⚠ Quadratic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 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

Generate All Subsequences — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler