Any combinatorics solution rather than DP?

Revision en2, by gagannagpal68, 2021-08-30 18:07:56

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)

  1. "aabbcc" 2 => 9( aa ab ac ba bb bc ca cb cc)

  2. "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.

Tags #combinatorics, #math, # dp, bitamasks

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)