“*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=

*. ( I will refer the three*

**3***s as a1,a2 and a3 just to distinguish them).*

**a**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?