1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
/**
 * Recursive approach (brute force)
 * Time Complexity: O(2^n) - Exponential in worst case
 * Space Complexity: O(m+n) - Recursion stack
 * 
 * @param {string} s - Source string
 * @param {string} t - Target string
 * @return {number} - Number of distinct subsequences
 */
function numDistinctRecursive(s, t) {
  function count(i, j) {
    // Base cases
    if (j === t.length) {
      return 1; // Found a valid subsequence
    }
    if (i === s.length) {
      return 0; // Can't form t
    }
    
    // If characters match, we have two choices
    if (s[i] === t[j]) {
      return count(i + 1, j + 1) + count(i + 1, j);
    } else {
      // If characters don't match, we can only skip s[i]
      return count(i + 1, j);
    }
  }
  
  return count(0, 0);
}
 
/**
 * Memoization approach (top-down dynamic programming)
 * Time Complexity: O(m*n) - Each subproblem computed once
 * Space Complexity: O(m*n) - For memoization and recursion stack
 * 
 * @param {string} s - Source string
 * @param {string} t - Target string
 * @return {number} - Number of distinct subsequences
 */
function numDistinctMemo(s, t) {
  const m = s.length;
  const n = t.length;
  
  // Create memo table
  const memo = Array(m + 1).fill().map(() => Array(n + 1).fill(-1));
  
  function count(i, j) {
    // Check memo
    if (memo[i][j] !== -1) {
      return memo[i][j];
    }
    
    // Base cases
    if (j === n) {
      return 1; // Found a valid subsequence
    }
    if (i === m) {
      return 0; // Can't form t
    }
    
    // If characters match, we have two choices
    if (s[i] === t[j]) {
      memo[i][j] = count(i + 1, j + 1) + count(i + 1, j);
    } else {
      // If characters don't match, we can only skip s[i]
      memo[i][j] = count(i + 1, j);
    }
    
    return memo[i][j];
  }
  
  return count(0, 0);
}
 
/**
 * Tabulation approach (bottom-up dynamic programming)
 * Time Complexity: O(m*n) - Fill 2D DP array
 * Space Complexity: O(m*n) - For the DP array
 * 
 * @param {string} s - Source string
 * @param {string} t - Target string
 * @return {number} - Number of distinct subsequences
 */
function numDistinctDP(s, t) {
  const m = s.length;
  const n = t.length;
  
  // Create DP array
  const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0));
  
  // Base case: empty string t is a subsequence of any string s
  for (let i = 0; i <= m; i++) {
    dp[i][0] = 1;
  }
  
  // Fill DP array
  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];
}
 
/**
 * Space-optimized dynamic programming approach
 * Time Complexity: O(m*n) - Process each character
 * Space Complexity: O(n) - 1D DP array
 * 
 * @param {string} s - Source string
 * @param {string} t - Target string
 * @return {number} - Number of distinct subsequences
 */
function numDistinct(s, t) {
  const n = t.length;
  
  // Create 1D DP array
  const dp = Array(n + 1).fill(0);
  dp[0] = 1; // Base case: empty string t is a subsequence of any string s
  
  // Process each character in s
  for (const char of s) {
    // Update DP array from right to left
    for (let j = n; j > 0; j--) {
      if (char === t[j - 1]) {
        dp[j] += dp[j - 1];
      }
    }
  }
  
  return dp[n];
}
 
// Test cases
console.log(numDistinct("rabbbit", "rabbit")); // 3
console.log(numDistinct("babgbag", "bag")); // 5