Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×
Any combinatorics solution rather than DP?
Difference between en1 and en2, changed 6 character(s)
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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English gagannagpal68 2021-08-30 18:07:56 6
en1 English gagannagpal68 2021-08-30 18:07:37 466 Initial revision (published)