"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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.