Leetcode Distinct Subsequences problem solution YASH PAL, 31 July 2024 In this Leetcode Distinct Subsequences problem solution we have Given two strings s and t, return the number of distinct subsequences of s which equals t. A string’s subsequence is a new string formed from the original string by deleting some (can be none) of the characters without disturbing the remaining characters’ relative positions. (i.e., “ACE” is a subsequence of “ABCDE” while “AEC” is not). It is guaranteed the answer fits on a 32-bit signed integer. Problem solution in Python. class Solution: def numDistinct(self, s: str, t: str) -> int: dp = [1] * (len(s) + 1) for r, t_char in enumerate(t, 1): prev, dp[0] = dp[0], 0 for c, s_char in enumerate(s, 1): curr = dp[c] dp[c] = dp[c-1] + (t_char == s_char and prev) prev = curr return dp[-1] Problem solution in Java. public int numDistinct(String s, String t) { int[] dp = new int[t.length()+1]; dp[0] = 1; for(int i=1;i<=s.length();i++) { int min = Math.min(i, t.length()); for(int j=min;j>=1;j--) { if(s.charAt(i-1) == t.charAt(j-1)) { dp[j] += dp[j-1]; } } } return dp[t.length()]; } Problem solution in C++. class Solution { public: int numDistinct(string s, string t) { int n = t.size(), m = s.size(); if(n>m)return 0; vector<vector<unsigned int>> dp(n,vector<unsigned int>(m,0)); for(int x=0; x<m; x++) { if(t[0] == s[x]) { dp[0][x] = dp[0][max(x-1,0)]+1; } else { dp[0][x] = dp[0][max(x-1,0)]; } } for(int x=1; x<n; x++) { for(int y=x; y<m; y++) { if(t[x] == s[y]) { dp[x][y] = dp[x-1][y-1]+dp[x][y-1]; } else { dp[x][y] = dp[x][y-1]; } } } return dp[n-1][m-1]; } }; Problem solution in C. int numDistinct(char* s, char* t) { int len1, len2; if((len1 = strlen(s)) == 0 || (len2 = strlen(t)) == 0){ return 0; } int dp[len2], i, j; int cur = 0; memset(dp, 0, sizeof(int) * len2); for(i = 0; i < len1; ++i){ if(cur != len2){ if(cur == 0){ if(s[i] == t[cur]){ dp[cur++] = 1; } continue; } for(j = cur; j > -1; --j){ if(t[j] == s[i]){ if(j == 0){ dp[j] = dp[j] + 1; continue; } dp[j] = dp[j] + 1 * dp[j-1]; if(j == cur){ cur++; } } } } else{ for(j = cur - 1; j > -1; --j){ if(t[j] == s[i]){ if(j == 0){ dp[j] = dp[j] + 1; continue; } dp[j] = dp[j] + 1 * dp[j-1]; } } } } return dp[len2-1]; } coding problems