What is the time complexity of Distinct Subsequences?

The optimal solution has a time complexity of O(m*n).

What data structures are used to solve Distinct Subsequences?

This problem uses String, Dynamic Programming. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Distinct Subsequences?

Insight 1: Dynamic programming is suitable because the number of distinct subsequences can be built up from smaller subproblems. Insight 2: The relationship dp[i][j] represents the number of distinct subsequences of s[0...i] which equals t[0...j].

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Distinct Subsequences - LeetCode 115 Solution

Q: Which companies ask LeetCode 115. Distinct Subsequences in interviews?

This problem is frequently asked at Coupang, MathWorks, Salesforce, TikTok, Trilogy and 1 more companies.

Distinct Subsequences - Complete Solution Guide

Distinct Subsequences is LeetCode problem 115, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Given two strings s and t, return the number of distinct subsequences of s which equals t. The test cases are generated so that the answer fits on a 32-bit signed integer. Example 1: Input: s = "rabbbit", t = "rabbit" Output: 3 Explanation: As shown below, there are 3 ways you can generate "rabbit" from s. rabb b it ra b bbit rab b bit Example 2: Input: s = "babgbag", t = "bag" Output: 5 Explanation: As shown below, there are 5 ways you can generate "bag" from s. ba b g bag ba bgba g b abgb ag b

Detailed Explanation

The problem asks us to find the number of distinct subsequences of string `s` that are equal to string `t`. 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. The task is to count how many different ways we can construct string `t` by selecting characters from string `s` in their original order.

Solution Approach

The solution employs dynamic programming to efficiently count the distinct subsequences. A 1D DP array `dp` of size `len(t) + 1` is used. `dp[j]` stores the number of distinct subsequences of the current prefix of `s` that match the prefix `t[0...j-1]`. The outer loop iterates through the `s` string, and the inner loop iterates backwards through the `t` string. If `s[i-1]` matches `t[j-1]`, it means we can either exclude `s[i-1]` or include it in forming the subsequence. Including it adds `dp[j-1]` to `dp[j]`, where `dp[j-1]` is the number of ways to form `t[0...j-2]` using `s[0...i-1]`. If `s[i-1]` doesn't match `t[j-1]`, we simply inherit the count from the previous state, meaning `dp[j]` remains unchanged for the current character in `s`.

Step-by-Step Algorithm

Step 1: Initialize a 1D DP array `dp` of size `len(t) + 1` with all elements set to 0. `dp[0]` is set to 1, as an empty string `t` always exists as a subsequence of any string `s` exactly once (by deleting all characters of `s`).
Step 2: Iterate through the string `s` from `i = 1` to `len(s)`. This represents considering each character of `s` one by one.
Step 3: For each character in `s`, iterate through the string `t` from `j = len(t)` down to `1`. Iterating backwards avoids overwriting values needed in the current iteration when calculating `dp[j]` from `dp[j-1]`.
Step 4: Inside the inner loop, check if `s[i - 1]` is equal to `t[j - 1]`. If they are equal, update `dp[j]` by adding `dp[j - 1]` to it. This means we can form the subsequence `t[0...j-1]` in two ways: by not including `s[i-1]` (already counted in `dp[j]`) or by including `s[i-1]` which requires `t[0...j-2]` to have been formed from `s[0...i-2]` which is `dp[j-1]`.
Step 5: If `s[i - 1]` is not equal to `t[j - 1]`, then `dp[j]` remains unchanged, as `s[i-1]` doesn't contribute to forming `t[0...j-1]`.
Step 6: After iterating through all characters of `s`, the final value of `dp[len(t)]` represents the total number of distinct subsequences of `s` that are equal to `t`.

Key Insights

Insight 1: Dynamic programming is suitable because the number of distinct subsequences can be built up from smaller subproblems.
Insight 2: The relationship dp[i][j] represents the number of distinct subsequences of s[0...i] which equals t[0...j].
Insight 3: Optimization is possible by reducing the space complexity from O(m*n) to O(n) by iterating backwards through the `t` string's indices.

Complexity Analysis

Time Complexity: O(m*n)

Space Complexity: O(n)

Topics

This problem involves: String, Dynamic Programming.

Companies

Asked at: Coupang, MathWorks, Salesforce, TikTok, Trilogy, Uber.

Distinct Subsequences | LeetCode 115

Hard

String Dynamic Programming

Time: O(m*n)Space: O(n)

Solution Code

Available in:

class Solution {
    public int numDistinct(String s, String t) {
        int len_s = s.length();
        int len_t = t.length();

        int[] dp = new int[len_t + 1];
        dp[0] = 1;

        for (int i = 1; i <= len_s; i++) {
            for (int j = len_t; j > 0; j--) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[j] += dp[j - 1];
                }
            }
        }

        return dp[len_t];
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 115: Distinct Subsequences - Detailed explanation and solution approaches.

Topics

String Dynamic Programming

Companies

CoupangMathWorksSalesforceTikTokTrilogyUber

Stats

Difficulty:Hard

Languages:4

Companies:6

Problem #:115

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

6 steps

1
Step 1: Initialize a 1D DP array `dp` of size `len(t) + 1` with all elements set to 0. `dp[0]` is set to 1, as an empty string `t` always exists as a subsequence of any string `s` exactly once (by deleting all characters of `s`).
2
Step 2: Iterate through the string `s` from `i = 1` to `len(s)`. This represents considering each character of `s` one by one.
3
Step 3: For each character in `s`, iterate through the string `t` from `j = len(t)` down to `1`. Iterating backwards avoids overwriting values needed in the current iteration when calculating `dp[j]` from `dp[j-1]`.
4
Step 4: Inside the inner loop, check if `s[i - 1]` is equal to `t[j - 1]`. If they are equal, update `dp[j]` by adding `dp[j - 1]` to it. This means we can form the subsequence `t[0...j-1]` in two ways: by not including `s[i-1]` (already counted in `dp[j]`) or by including `s[i-1]` which requires `t[0...j-2]` to have been formed from `s[0...i-2]` which is `dp[j-1]`.
5
Step 5: If `s[i - 1]` is not equal to `t[j - 1]`, then `dp[j]` remains unchanged, as `s[i-1]` doesn't contribute to forming `t[0...j-1]`.
6
Step 6: After iterating through all characters of `s`, the final value of `dp[len(t)]` represents the total number of distinct subsequences of `s` that are equal to `t`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(m*n)

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The time complexity arises from the nested loops. The outer loop iterates `m` times, and the inner loop iterates `n` times. The space complexity is determined by the size of the DP array, which has a length of `n+1`.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

2D Dynamic Programming

A more intuitive approach is to use a 2D DP table `dp[i][j]` to store the number of distinct subsequences of `s[0...i]` that equal `t[0...j]`. The transitions are: if `s[i] == t[j]`, then `dp[i][j] = dp[i-1][j-1] + dp[i-1][j]`. If `s[i] != t[j]`, then `dp[i][j] = dp[i-1][j]`.

Time: O(m*n)Space: O(m*n)

Trade-offs: The 2D DP approach is easier to understand but uses more space than the optimized 1D DP approach. The 1D DP version optimizes space by iterating through the inner loop in reverse order which avoids incorrect updates by overwriting previous state variables.

✨

Key Insights

1Insight 1: Dynamic programming is suitable because the number of distinct subsequences can be built up from smaller subproblems.
2Insight 2: The relationship dp[i][j] represents the number of distinct subsequences of s[0...i] which equals t[0...j].
3Insight 3: Optimization is possible by reducing the space complexity from O(m*n) to O(n) by iterating backwards through the `t` string's indices.

📚

Key Terms Explained

For Students

Dynamic Programming

Breaking complex problems into smaller subproblems and storing results.

String

A sequence of characters. Like a word or sentence in programming!

Edge Cases

Edge case 1: Empty string `t`. The DP array is initialized such that `dp[0] = 1`, meaning an empty string `t` exists as a subsequence of any string `s` exactly once. This handles the case where `t` is an empty string, although the constraints prevent it.
Edge case 2: `s` or `t` is `null` or empty (outside the constraints). The provided code assumes that strings are not null or empty. It should be validated for handling such cases if needed.
Edge case 3: `s` is shorter than `t`. The algorithm handles this implicitly; if `s` is too short to form `t`, `dp[len(t)]` will remain 0, which is the correct answer.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not initializing `dp[0] = 1`. This is essential because it represents the base case where an empty subsequence can be formed from any string.

✗Common mistake 2: Iterating through the inner loop in the wrong direction when using the 1D DP approach. Iterating forwards will overwrite values prematurely, leading to an incorrect result.

✗Common mistake 3: Confusing subsequence with substring. A substring is a contiguous sequence of characters within a string, while a subsequence can have gaps.

✗Common mistake 4: Integer overflow. While the problem states the answer fits in a 32-bit integer, intermediate calculations *can* exceed this limit if the constraints were larger. The C++ code used double to mitigate this, and while the problem statement guarantees that the *final result* fits in an `int`, it might be safer to use `long` or `long long`.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Bioinformatics - Finding the number of ways a particular DNA sequence (t) can be formed from a larger DNA sequence (s), allowing for mutations or insertions.

🏦Real-world scenario 2: Text Editing - Determining the edit distance or similarity between two strings, particularly in spell checkers or auto-completion systems. This is closely related, though edit distance usually allows for insertions, deletions, and substitutions, while this problem only considers deletions.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

String problems often involve sliding windows or two pointers. Consider if the character set is limited (lowercase letters = only 26 possibilities).

🎯 Interview Tip

It's okay to not finish hard problems in interviews. Show your problem-solving process.

⚠️ Watch Out

Mutating strings directly in languages where strings are immutable. Use StringBuilder or arrays.

👨‍💻 From Experience

I encountered a variation of this problem in a system design interview. The key was recognizing the underlying pattern.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: September 24, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 13

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 6

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJun 29

❓

Frequently Asked Questions

What is the sliding window technique for string problems?

Sliding window maintains a "window" of characters with two pointers. Expand the right pointer to include characters, shrink from left when window violates constraints. Useful for substring problems, anagrams, and longest/shortest substring with properties.

Should I use top-down (memoization) or bottom-up (tabulation)?

Start with top-down (recursion + memoization) as it directly maps to the recursive thinking and handles only needed subproblems. Convert to bottom-up for better space efficiency and to avoid stack overflow. Bottom-up is often faster due to no recursion overhead.

Is it okay to not fully solve hard problems in interviews?

Yes! Interviewers care more about your problem-solving process than the final answer. Demonstrate: clear communication, systematic approach, ability to recognize when to pivot strategies, and graceful handling of hints. Partial progress with good reasoning is valued.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Distinct Subsequences"?

For this hard-level String problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether dynamic programming techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?