115. Distinct Subsequences LeetCode Solution

In this guide, you will get 115. Distinct Subsequences LeetCode Solution with the best time and space complexity. The solution to Distinct Subsequences problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Distinct Subsequences solution in C++
Distinct Subsequences solution in Java
Distinct Subsequences solution in Python
Additional Resources

115. Distinct Subsequences LeetCode Solution image

Problem Statement of Distinct Subsequences

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

Example 2:

Input: s = “babgbag”, t = “bag”
Output: 5
Explanation:
As shown below, there are 5 ways you can generate “bag” from s.
babgbag
babgbag
babgbag
babgbag
babgbag

Constraints:

1 <= s.length, t.length <= 1000
s and t consist of English letters.

Complexity Analysis

Time Complexity: O(mn)
Space Complexity: O(mn)

115. Distinct Subsequences LeetCode Solution in C++

class Solution {
 public:
  int numDistinct(string s, string t) {
    const int m = s.length();
    const int n = t.length();
    vector<vector<unsigned long>> dp(m + 1, vector<unsigned long>(n + 1));

    for (int i = 0; i <= m; ++i)
      dp[i][0] = 1;

    for (int i = 1; i <= m; ++i)
      for (int j = 1; j <= n; ++j)
        if (s[i - 1] == t[j - 1])
          dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
        else
          dp[i][j] = dp[i - 1][j];

    return dp[m][n];
  }
};
/* code provided by PROGIEZ */

115. Distinct Subsequences LeetCode Solution in Java

class Solution {
  public int numDistinct(String s, String t) {
    final int m = s.length();
    final int n = t.length();
    long[][] dp = new long[m + 1][n + 1];

    for (int i = 0; i <= m; ++i)
      dp[i][0] = 1;

    for (int i = 1; i <= m; ++i)
      for (int j = 1; j <= n; ++j)
        if (s.charAt(i - 1) == t.charAt(j - 1))
          dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
        else
          dp[i][j] = dp[i - 1][j];

    return (int) dp[m][n];
  }
}
// code provided by PROGIEZ

115. Distinct Subsequences LeetCode Solution in Python

class Solution:
  def numDistinct(self, s: str, t: str) -> int:
    m = len(s)
    n = len(t)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
      dp[i][0] = 1

    for i in range(1, m + 1):
      for j in range(1, n + 1):
        if s[i - 1] == t[j - 1]:
          dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
        else:
          dp[i][j] = dp[i - 1][j]

    return dp[m][n]
 # code by PROGIEZ