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

Spread the love

Close-up of a laptop and tablet on a wooden desk, showcasing modern technology.

Table of Contents

Problem Statement: Distinct Subsequences

Given two strings s and t, return the number of distinct subsequences of s that equals t. A subsequence of a string is a new string formed from the original string by deleting some (or no) characters without changing the relative order of the remaining characters.

For example, if s = "rabbbit" and t = "rabbit", the number of distinct subsequences is 3.

Approach

This problem can be solved using Dynamic Programming (DP). The idea is to maintain a 2D table dp[i][j] where:

i represents the first i characters of s.
j represents the first j characters of t.

dp[i][j] stores the number of ways to form the first j characters of t from the first i characters of s.

Recurrence Relation:

If s[i-1] == t[j-1], we have two options:
- Include s[i-1] as part of the subsequence forming t[j-1], or
- Exclude it.
Thus, the recurrence relation becomes:cssCopy codedp[i][j] = dp[i-1][j-1] + dp[i-1][j]
If s[i-1] != t[j-1], we can only exclude s[i-1] from the subsequence:cssCopy codedp[i][j] = dp[i-1][j]

Base Case:

dp[0][0] = 1 (An empty string can match another empty string).
dp[i][0] = 1 for all i (An empty string t can be formed from any prefix of s by deleting all characters).
dp[0][j] = 0 for all j > 0 (An empty string s cannot form any non-empty string t).

Time Complexity:

The time complexity is O(m * n), where m is the length of string s and n is the length of string t.

Space Complexity:

The space complexity is O(m * n), where m is the length of string s and n is the length of string t.

Code in Multiple Languages

C:

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

int numDistinct(char* s, char* t) {
    int m = strlen(s);
    int n = strlen(t);
    
    int dp[m + 1][n + 1];
    
    // Base case initialization
    for (int i = 0; i <= m; i++) {
        dp[i][0] = 1; // An empty string t can be formed from any prefix of s
    }
    
    for (int j = 1; j <= n; j++) {
        dp[0][j] = 0; // An empty string s cannot form a non-empty t
    }
    
    // Fill the dp table
    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";
    char t[] = "rabbit";
    printf("%d\n", numDistinct(s, t)); // Output: 3
    return 0;
}

C++:

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int numDistinct(string s, string t) {
    int m = s.size(), n = t.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    
    for (int i = 0; i <= m; i++) {
        dp[i][0] = 1; // An empty t can be formed from any prefix of 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() {
    string s = "rabbbit", t = "rabbit";
    cout << numDistinct(s, t) << endl; // Output: 3
    return 0;
}

Java:

public class DistinctSubsequences {
    public static int numDistinct(String s, String t) {
        int m = s.length(), n = t.length();
        int[][] dp = new int[m + 1][n + 1];
        
        // Initialize base case
        for (int i = 0; i <= m; i++) {
            dp[i][0] = 1; // An empty string t can be formed from any prefix of s
        }
        
        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(numDistinct(s, t)); // Output: 3
    }
}

Python:

def numDistinct(s: str, t: str) -> int:
    m, n = len(s), len(t)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Base case
    for i in range(m + 1):
        dp[i][0] = 1  # An empty t can be formed from any prefix of s
    
    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]

# Example usage
s = "rabbbit"
t = "rabbit"
print(numDistinct(s, t))  # Output: 3

C#:

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];
        
        // Initialize base case
        for (int i = 0; i <= m; i++) {
            dp[i, 0] = 1;  // An empty t can be formed from any prefix of 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];
    }

    static void Main() {
        string s = "rabbbit";
        string t = "rabbit";
        Console.WriteLine(NumDistinct(s, t));  // Output: 3
    }
}

JavaScript:

function numDistinct(s, t) {
    const m = s.length, n = t.length;
    const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
    
    // Base case
    for (let i = 0; i <= m; i++) {
        dp[i][0] = 1; // An empty t can be formed from any prefix of s
    }
    
    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];
}

// Example usage
const s = "rabbbit", t = "rabbit";
console.log(numDistinct(s, t));  // Output: 3

Summary:

This solution uses Dynamic Programming to efficiently solve the problem of finding distinct subsequences. The idea is to build a 2D table dp that records how many ways the string t can be formed from any prefix of string s. Each of the implementations in C, C++, Java, Python, C#, and JavaScript follows the same approach with appropriate syntax for the respective language.