Distinct Subsequences In C,CPP,JAVA,PYTHON,C#,JS

/ DSA / By
Spread the love

The problem “Distinct Subsequences“ asks for the number of distinct subsequences of a string s that match a string t. This is a well-known dynamic programming problem and can be efficiently solved using a 2D dynamic programming table.

Problem Statement:

Given a string s and a string t, find the number of distinct subsequences of s which equals t.

A subsequence is derived from another string by deleting some or no characters without changing the order of the remaining characters.

Example 1:

Input:

s = "rabbbit", t = "rabbit"

Output:

3

Explanation: There are three distinct subsequences of “rabbbit” which equal “rabbit”:

  • “rabbbit” -> “rabbit”
  • “rabbbit” -> “rabbit”
  • “rabbbit” -> “rabbit”

Example 2:

Input:

s = "axaxb", t = "ab"

Output:

4

Explanation: There are four distinct subsequences of “axaxb” which equal “ab”:

  • “axaxb” -> “ab”
  • “axaxb” -> “ab”
  • “axaxb” -> “ab”
  • “axaxb” -> “ab”

Approach:

We use a dynamic programming approach to solve this problem.

Let dp[i][j] represent the number of ways to form the first j characters of t using the first i characters of s. The recurrence relation is as follows:

  • Base Case:
    • dp[i][0] = 1 for all i, because there’s exactly one way to match an empty string t (by taking no characters).
    • dp[0][j] = 0 for all j > 0, because you cannot form a non-empty t from an empty s.
  • Recurrence:
    • If s[i-1] == t[j-1], then:
      • dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
        • dp[i-1][j-1] corresponds to the case where we match the current characters of s and t.
        • dp[i-1][j] corresponds to the case where we skip the current character of s.
    • If s[i-1] != t[j-1], then:
      • dp[i][j] = dp[i-1][j]
        • We skip the current character of s.

The final answer is dp[len(s)][len(t)].

Time Complexity:

  • Time Complexity: O(m * n), where m is the length of s and n is the length of t.
  • Space Complexity: O(m * n) for the dynamic programming table.

Now, let’s implement this solution in different languages.

C Code:

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

int numDistinct(char *s, char *t) {
    int m = strlen(s), n = strlen(t);
    int dp[m+1][n+1];

    // Initialize the dp array
    for (int i = 0; i <= m; i++) {
        dp[i][0] = 1; // There's 1 way to form empty t
    }
    for (int j = 1; j <= n; j++) {
        dp[0][j] = 0; // There's no way to form a non-empty t from empty s
    }

    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];
}

int main() {
    char s[] = "rabbbit", t[] = "rabbit";
    printf("Number of distinct subsequences: %d\n", numDistinct(s, t));
    return 0;
}

C++ Code:

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int numDistinct(string s, string t) {
    int m = s.length(), n = t.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    // Base case: dp[i][0] = 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];
}

int main() {
    string s = "rabbbit", t = "rabbit";
    cout << "Number of distinct subsequences: " << numDistinct(s, t) << endl;
    return 0;
}

Java Code:

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

        // Base case: dp[i][0] = 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 dp[m][n];
    }

    public static void main(String[] args) {
        String s = "rabbbit", t = "rabbit";
        System.out.println("Number of distinct subsequences: " + numDistinct(s, t));
    }
}

Python Code:

def numDistinct(s, t):
    m, n = len(s), len(t)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Base case: dp[i][0] = 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]

# Test case
s = "rabbbit"
t = "rabbit"
print("Number of distinct subsequences:", numDistinct(s, t))

C# Code:

using System;

class Program {
    public static int NumDistinct(string s, string t) {
        int m = s.Length, n = t.Length;
        int[,] dp = new int[m + 1, n + 1];

        // Base case: dp[i][0] = 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];
    }

    static void Main() {
        string s = "rabbbit", t = "rabbit";
        Console.WriteLine("Number of distinct subsequences: " + NumDistinct(s, t));
    }
}

JavaScript Code:

function numDistinct(s, t) {
    const m = s.length, n = t.length;
    let dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0));

    // Base case: dp[i][0] = 1
    for (let i = 0; i <= m; i++) {
        dp[i][0] = 1;
    }

    for (let i = 1; i <= m; i++) {
        for (let 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];
}

// Test case
const s = "rabbbit", t = "rabbit";
console.log("Number of distinct subsequences:", numDistinct(s, t));

Summary:

This problem can be efficiently solved using dynamic programming, and the code above provides solutions for C, C++, Java, Python, C#, and JavaScript. The time complexity for all the solutions is O(m×n)O(m \times n)O(m×n), where mmm and nnn are the lengths of strings s and t, respectively.