Problem statement

https://binarysearch.com/problems/Subsequence-Picking/

Solution

This problem is similar to Leetcode 940. Distinct Subsequences II, but here we need to count number of unique subsequences of each length. We need to use the best complexity solution to make it pass. Idea is similar, but we keep in dp[i] number of unique subsequences for each length [0, ..., n] which use symbols S[:i]. In the end we need to go through dp[-1][::-1] and count number of subsequences.

Complexity

Time complexity is O(n^2 + k) (can be made O(n^2)), space complexity is O(n^2).

Code

class Solution:
    def solve(self, s, k):
        n = len(s)
        dp, last = [[1] + [0]*n], {}
        for i, x in enumerate(s):
            dp.append([i+j for i,j in zip(dp[-1], [0] + dp[-1])])
            if x in last:
                for j in range(n):
                    dp[-1][j+1] -= dp[last[x]][j]
            
            last[x] = i

        cands = dp[-1][::-1]
        if k >= sum(cands): return -1

        idx, ans = 0, 0
        for _ in range(k):
            if cands[idx] == 0: idx += 1
            cands[idx] -= 1
            ans += idx

        return ans