Distinct Subsequences

                                            
class Solution {
public:
    int numDistinct(string s, string t) {
        int m = s.length(), n = t.length();
        vector<vector<unsigned int>> dp(n + 1, vector<unsigned int>(m + 1, 0));
        
        for (int j = 0; j <= m; ++j) {
            dp[0][j] = 1;
        }
        
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (t[i - 1] == s[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];
                } else {
                    dp[i][j] = dp[i][j - 1];
                }
            }
        }
        
        return dp[n][m];
    }
};

                                            
class Solution {
    public int numDistinct(String s, String t) {
        int m = s.length();
        int n = t.length();
        
        int[][] dp = new int[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++) {
                dp[i][j] = dp[i - 1][j];
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] += dp[i - 1][j - 1];
                }
            }
        }
        
        return dp[m][n];
    }
}

                                            
class Solution(object):
    def numDistinct(self, s, t):
        dp = [[0] * (len(s) + 1) for _ in range(len(t) + 1)]
        for i in range(len(s) + 1):
            dp[0][i] = 1
        for i in range(1, len(t) + 1):
            for j in range(1, len(s) + 1):
                if t[i - 1] == s[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1]
                else:
                    dp[i][j] = dp[i][j - 1]
        return dp[-1][-1]

                                            
int numDistinct(char* s, char* t) {
    int m = strlen(s);
    int n = strlen(t);
    unsigned int dp[m + 1][n + 1];
    
    for (int i = 0; i <= m; i++) {
        dp[i][0] = 1;
    }
    
    for (int i = 1; i <= n; i++) {
        dp[0][i] = 0;
    }
    
    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];
}
\

                                            
public class Solution {
    public int NumDistinct(string s, string t) {
        int m = s.Length;
        int n = t.Length;

        int[,] dp = new int[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++) {
                dp[i, j] = dp[i - 1, j];
                if (s[i - 1] == t[j - 1]) {
                    dp[i, j] += dp[i - 1, j - 1];
                }
            }
        }

        return dp[m, n];
    }
}

                                            
/**
 * @param {string} s
 * @param {string} t
 * @return {number}
 */
var numDistinct = function(s, t) {
    const dp = Array(t.length + 1).fill(0);
    dp[0] = 1;
    
    for (let i = 1; i <= s.length; i++) {
        for (let j = t.length; j >= 1; j--) {
            if (s[i - 1] === t[j - 1]) {
                dp[j] += dp[j - 1];
            }
        }
    }
    
    return dp[t.length];
};

                                            
function numDistinct(s: string, t: string): number {
    const dp: number[][] = Array.from({ length: t.length + 1 }, () => Array(s.length + 1).fill(0));
    for (let i = 0; i <= s.length; i++) {
        dp[0][i] = 1;
    }
    for (let i = 1; i <= t.length; i++) {
        for (let j = 1; j <= s.length; j++) {
            if (t[i - 1] === s[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];
            } else {
                dp[i][j] = dp[i][j - 1];
            }
        }
    }
    return dp[t.length][s.length];
};

                                            
class Solution {
    /**
     * @param String $s
     * @param String $t
     * @return Integer
     */
    function numDistinct($s, $t) {
        $m = strlen($t);
        $n = strlen($s);
        $dp = array_fill(0, $m + 1, 0);
        $dp[0] = 1;
        
        for ($i = 1; $i <= $n; $i++) {
            for ($j = $m; $j > 0; $j--) {
                if ($t[$j - 1] == $s[$i - 1]) {
                    $dp[$j] += $dp[$j-1];
                }
            }
        }
        
        return $dp[$m];
    }
}

                                            
class Solution {
    fun numDistinct(s: String, t: String): Int {

        val dp = Array(t.length + 1) { IntArray(s.length + 1) }
        for (i in 0..s.length) dp[0][i] = 1

        for (i in 1..t.length) {
            for (j in 1..s.length) {
                dp[i][j] = dp[i][j - 1] + if (t[i - 1] == s[j - 1]) dp[i - 1][j - 1] else 0
            }
        }

        return dp[t.length][s.length]
    }
}

                                            
class Solution {
  int numDistinct(String s, String t) {
    int m = s.length;
    int n = t.length;
    
    List<List<int>> dp = List.generate(m + 1, (_) => List.filled(n + 1, 0));
    
    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];
  }
}

                                            
func numDistinct(s string, t string) int {
	dp := make([][]int, len(t)+1)
	for i := range dp {
		dp[i] = make([]int, len(s)+1)
	}

	for j := range dp[0] {
		dp[0][j] = 1
	}

	for i := 1; i <= len(t); i++ {
		for j := 1; j <= len(s); j++ {
			if s[j-1] == t[i-1] {
				dp[i][j] = dp[i-1][j-1] + dp[i][j-1]
			} else {
				dp[i][j] = dp[i][j-1]
			}
		}
	}

	return dp[len(t)][len(s)]
}

                                            
# @param {String} s
# @param {String} t
# @return {Integer}
def num_distinct(s, t)
    m, n = s.length, t.length
    dp = Array.new(m+1) { Array.new(n+1, 0) }
    
    (0..m).each { |i| dp[i][0] = 1 }
    
    (1..m).each do |i|
        (1..n).each do |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]
            end
        end
    end
    
    return dp[m][n]
end

                                            
object Solution {
    def numDistinct(s: String, t: String): Int = {
        val dp = Array.fill(t.length + 1)(Array.fill(s.length + 1)(0))
        for (j <- 0 to s.length) {
            dp(0)(j) = 1
        }
        
        for (i <- 1 to t.length; j <- 1 to s.length) {
            if (t(i - 1) == s(j - 1)) {
                dp(i)(j) = dp(i - 1)(j - 1) + dp(i)(j - 1)
            } else {
                dp(i)(j) = dp(i)(j - 1)
            }
        }
        
        dp(t.length)(s.length)
    }
}

                                            
impl Solution {
    pub fn num_distinct(s: String, t: String) -> i32 {
        let s = s.chars().collect::<Vec<char>>();
        let t = t.chars().collect::<Vec<char>>();
        
        let m = s.len();
        let n = t.len();
        
        let mut dp = vec![vec![0; n + 1]; m + 1];
        
        for i in 0..=m {
            dp[i][0] = 1;
        }
        
        for i in 1..=m {
            for j in 1..=n {
                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];
                }
            }
        }
        
        dp[m][n]
    }
}

                                            
(define/contract (num-distinct s t)
  (-> string? string? exact-integer?)
  (define (helper sIdx tIdx)
    (cond
      ((= tIdx (string-length t)) 1)
      ((= sIdx (string-length s)) 0)
      ((char=? (string-ref s sIdx) (string-ref t tIdx))
       (+ (helper (add1 sIdx) (add1 tIdx))
          (helper (add1 sIdx) tIdx)))
      (else
       (helper (add1 sIdx) tIdx))))
  (helper 0 0)
  )

To solve this coding challenge of finding the number of distinct subsequences of one string \( s \) that equal another string \( t \), we will employ dynamic programming. This approach helps in breaking down the problem into simpler subproblems and building up the solution step-by-step.

# Explanation

Problem Breakdown

The problem asks us to count the number of ways to derive string \( t \) from \( s \) by deleting some or no characters without changing the order of the remaining characters.

Key Points:

A subsequence is derived by deleting some or no characters from a string without changing the order of the remaining characters.
We need to find distinct subsequences in \( s \) that are equal to \( t \).

Dynamic Programming Approach:

Initialization : We will utilize a 2D array \( dp \) where \( dp[i][j] \) represents the number of ways to form the first \( i \) characters of \( t \) from the first \( j \) characters of \( s \).
Base Case : When \( t \) is an empty string, there is one way to match it with any prefix of \( s \) by deleting all characters of \( s \). Hence, \( dp[0][j] = 1 \) for all \( 0 \leq j \leq \text{len}(s) \).
Filling the Table :

If the characters of \( t \) and \( s \) match (i.e., \( t[i-1] == s[j-1] \)), then either we consider this match or we don’t.

dp[i][j] = dp[i-1][j-1] + dp[i][j-1]

If they don’t match, then we simply carry forward the number of ways to form \( t \) without the current character of \( s \):

dp[i][j] = dp[i][j-1]

Final Result:

The result will be stored in \( dp[\text{len}(t)][\text{len}(s)] \), representing the number of ways to form the entire string \( t \) using all characters of \( s \).

Step-by-Step Explanation of Pseudocode

Create and initialize the DP table :

                                            
Initialize dp table with dimensions (len(t) + 1) x (len(s) + 1) to all zeros

# Base Case: An empty t can be matched with any prefix of s by deleting all characters of s
For j from 0 to len(s):
dp[0][j] = 1

Fill the DP table using nested loops :

                                            
For i from 1 to len(t):
For j from 1 to len(s):
If t[i-1] == s[j-1]:  # Characters match
dp[i][j] = dp[i-1][j-1] + dp[i][j-1]
Else:  # Characters don't match
dp[i][j] = dp[i][j-1]

Return the result :

                                            
Return dp[len(t)][len(s)]

Detailed Steps in Pseudocode

Initialize the DP Table

                                            
# Create a 2D list with (len(t) + 1) rows and (len(s) + 1) columns initialized with zeros
dp = [[0 for _ in range(len(s) + 1)] for _ in range(len(t) + 1)]

# Initialize the base case where the first row is filled with 1s
For j from 0 to len(s):
    dp[0][j] = 1  # There's exactly one way to match an empty substring t with any s's prefix by deleting all characters

Fill the DP Table

                                            
# Iterate over each character in t
For i from 1 to len(t):
    # Iterate over each character in s
    For j from 1 to len(s):
        If t[i-1] == s[j-1]:
            # Sum of ways: considering the current character match + not considering the current match
            dp[i][j] = dp[i-1][j-1] + dp[i][j-1]
        Else:
            # Carry forward the previous count without considering the current character of s
            dp[i][j] = dp[i][j-1]

Retrieve the Final Result

                                            
# The number of distinct subsequences that match t from s is found in the last cell
Return dp[len(t)][len(s)]

By following this detailed methodology, you can efficiently solve the problem of counting distinct subsequences using a dynamic programming approach.