"This is the official page of DSAwithPrinceSingh. This page contains the Dynamic Programming (DP) classic question code in Python and C++ that we learned on our website in the DP section. Here, you can access all the code from the entire DP section.”

32 Distinct Subsequences Space Optimization Using Single Array

class Solution:
    def SpaceOptimizationApproach(self, str1, index1, str2, index2, prev):
        # TODO: Single array Space Optimization Approach
        # Base Case: if we return 1 when index2 < 0
        prev[0] = 1

        for indx1 in range(1, index1 + 1):
            for indx2 in range(index2, 0, -1):
                if str1[indx1 - 1] == str2[indx2 - 1]:
                    pickedIndex2 = prev[indx2 - 1]
                    notPickedIndex2 = prev[indx2]
                    prev[indx2] = pickedIndex2 + notPickedIndex2
                else:
                    prev[indx2] = prev[indx2]

        return prev[index2]

    def numDistinct(self, s, t):
        i = len(s)
        j = len(t)
        prev = [0] * (j + 1)
        return self.SpaceOptimizationApproach(s, i, t, j, prev)

ans = Solution()
s = "rabbbit"
t = "rabbit"
print(ans.numDistinct(s, t))

"This page is currently under development. We are actively working on it, and it will be completed soon.”