# Number of subsequence with k distinct characters

"A string is a subsequence of a given string, that is generated by deleting some(possibly zero) character of a given string without changing its order."

Suppose we have string s="aabca" and k=3. ( I will refer the three as as a1,a2 and a3 just to distinguish them). So number of subsequence with 3 distinct characters are -

7 => (a1)bc, (a2)bc, bc(a3), (a1)(a2)bc, (a1)bc(a3), (a2)bc(a3), (a1)(a2)bc(a3)

I know how to calculate the answer for number of substring with k distinct character. How to do it for subsequence?

Suppose there are $$c$$ types of balls, and there are $$n_i$$ balls of type $$i$$. Let $$S$$ be a set of types of balls. In how many ways can we choose balls so that only balls of type $$S$$ appear, and at least one ball of type $$i$$ appears for each $$i \in S$$? The answer is clearly $$\prod_{i \in S} (2^{n_i} - 1).$$ Taking $$S = \{1,\ldots,c\}$$, we get a solution to your problem in the case where $$k$$ is the number of different characters in the original string (in your example, $$n_1 = 3$$ and $$n_2=n_3=1$$).
You are interested in the value of the above when summed over all sets $$S$$ of size $$k$$. This is the coefficient of $$x^k$$ in the generating function $$\prod_{i=1}^c (1 + (2^{n_i}-1)x).$$ This coefficient can be computed using dynamic programming. Details left to you.