115. Distinct Subsequences | silvermete0r's solution (hardcoded)

# https://leetcode.com/problems/distinct-subsequences/description/

import math
from bisect import bisect_right
from collections import defaultdict

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        if len(s) < len(t): return 0
        if len(s) == len(t): return int(s == t)
        st, tt = set(s), set(t)
        if st == tt and len(st) == 1:
            sl, tl = len(s), len(t)
            return int(math.comb(sl, tl))
        inds = defaultdict(list)
        n = len(s)
        for i in range(n):
            inds[s[i]].append(i)
        t = t[::-1]
        dp = [0] * n
        for i in inds[t[0]]:
            dp[i] = 1
        for k in range(1, len(t)):
            new_vals = []
            for i in inds[t[k]]:
                v = 0
                pos = bisect_right(inds[t[k-1]], i)
                for j in inds[t[k-1]][pos:]:
                    v += dp[j]
                if v > 0:
                    new_vals.append((i, v))
            new_inds = []
            for ind, new_val in new_vals:
                dp[ind] = new_val
                new_inds.append(ind)
            inds[t[k]] = new_inds
        ans = 0
        for ind in inds[t[-1]]:
            ans += dp[ind]
        return ans