### sandeep007's blog

By sandeep007, history, 17 months ago,

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.

• 0

 » 17 months ago, # |   +9 Is that a stars and bars problem!
 » 17 months ago, # |   +16 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.
•  » » 17 months ago, # ^ | ← Rev. 2 →   +8 This is $O(k)$?What if there are $Q \le 10^5$ queries of this type with different frequencies and $k$?
•  » » » 17 months ago, # ^ |   0 My solution is 26 * O(k) total, yes.That's significantly harder. I don't have a solution for you