sandeep007's blog

How to solve this combinatorics problem ?
By sandeep007, history, 6 years ago, In English

Given the frequency of each lowercase character f(a), f(b)... f(z) and k. Compute the number of unique strings of length k having sorted characters.

k <= 10^5

Sum(f(i)) <= 10^5

Please provide Hints/Approach to solve this problem.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Is that a stars and bars problem!

→ Reply
»
6 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Let's make a dp state that is (current char, string index) that stores the count. When we move to the next char, we need the sum of the last f(char) items for our new value at a given index. We can calculate these in O(1) by doing a prefix sum on the last row of our dp.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    This is $$$O(k)$$$?
    What if there are $$$Q \le 10^5$$$ queries of this type with different frequencies and $$$k$$$?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My solution is 26 * O(k) total, yes.

      That's significantly harder. I don't have a solution for you

      → Reply