Solution:
Let us represent the string to c.
First, we can notice that: for i<j, there must be $c_{s[i]}\leq c_{s[j]}$. For example, $[3,2,4,1,0,5,6]$, at least we have $c_3\leq c_2\leq c_4\leq c_1\leq c_0\leq c_5\leq c_6$.
Consider the string is made by n different letters. If so, we only need make sure the letters are sorted by the permutation above. So, there are $C_k^n$ solutions. (If k<n, then there is 0 solution.)
If the string is made by less than n letters, so that there must be duplicate character in the string. So, we can find that i and j which: $i<j$ and $c_{s[i]}=c_{s[j]}$. So, when sort lexicographically, we have: $c_{s[i] + 1}<c_{s[j]+1}$, or $c_{s[i]+1}=c_{s[j]+1}$ but $c_{s[i]+2}<c_{s[j]+2}$, and so on.
Note that: if $c_{s[i]+1}=c_{s[j]+1}$ and $c_{s[i]+2}<c_{s[j]+2}$, then in the s, the index of s[i]+1 must smaller than index of s[j]+1.
So, for $i<j$, if and only if $index(s[i]+1)<index(s[j]+1)$, $c_{s[i]}=c_{s[j]}$ is possible. (Where $index(x)$ represent the index of x-th suffix string in s).
For example, $[3,2,4,1,0,5,6]$. We found that $c_3<c_2$ (So, $c_3$ cannot equal to $c_2$), because $index(3+1)=index(4)=2>0=index(3)=index(2+1)$. But $c_2\leq c_4$ (So, $c_2$ can equal to $c_4$), because $index(2+1)=index(3)=0<5=index(5)=index(4+1)$.
For $c_5$ and $c_6$ which is a little special. It is not hard to find that, when sort lexicographically, if $c_5=c_6$, then must have $index(6)<index(5)$. So, the end character of string always in the front. So, it is ok to define $index(n)=index(7)=-1$.
So for $[3,2,4,1,0,5,6]$, we have $c_3< c_2\leq c_4< c_1\leq c_0\leq c_5<c_6$.
So, for $[3,2,4,1,0,5,6]$, we can choose 4 letters, so that $c_3< c_2= c_4< c_1= c_0=c_5<c_6$. Also, we can choose 5 letters, which require 2 of 3 positions must be equal. Also, can choose 6 letters, which 1 of 3 position must be equal.
So, for $[3,2,4,1,0,5,6]$, the result is: $C_6^6\cdot C_3^1 + C_6^5\cdot C_3^2+C_6^4\cdot C_3^3=1\cdot3+6\cdot 3 + 15\cdot 1=36$.
Code:
Java
C++
