Given a string s and a number k. You need to tell count of distinct string of length k. s.t. k is a subset of s. Eg 1. "aaabb" 2 => 4 (aa bb ab ba) 2. "aabbcc" 2 => 9( aa ab ac ba bb bc ca cb cc) 3. "abbcc" 2 => 8( same as #2 but aa can't be formed

I can create a dp of state index and mask where mask is of base 26 and rest is straightforward. Please help me in finding some combinatorics approach of solving it.