Dynamic Programming - Distinct Subsequences

Given strings s and t, return the number of distinct subsequences of s which equals t.

Input: s="rabbbit", t="rabbit" → Output: 3

Input: s="babgbag", t="bag" → Output: 5

dp[i][j] = number of ways to form t[0..j-1] from s[0..i-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].

dp[i][0] = 1 (empty t matched by any prefix of s).
dp[0][j] = 0 for j > 0.
Fill table: if match, add both using current s char and skipping it.
Return dp[m][n].

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

Time Complexity: O(M*N)
Space Complexity: O(M*N)