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)
"aabbcc" 2 => 9( aa ab ac ba bb bc ca cb cc)
"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.