2026-01-08 17:17:32 +0300 MSK

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        cache = {}
        length1, length2 = len(s), len(t)

        def dp(i: int, j: int) -> int:
            if j == length2:
                return 1
            if i == length1:
                return 0
            key = (i, j)
            if key in cache:
                return cache[key]
            res = 0
            if s[i] == t[j]:
                res += dp(i + 1, j+ 1)
            res += dp(i + 1, j)
            cache[key] = res
            return res

        return dp(0, 0)