0
$\begingroup$

I came across the following question on SPOJ.

Find the number of strings of length “N” made up of only 3 characters – a, b, c such that “a” occurs at least “min_a” times and at most “max_a” times, “b” occurs at least “min_b” times and at most “max_b” times and “c” occurs at least “min_c” times and at most “max_c” times. Note that all permutations of same string count as 1, so “abc” is same as “bac”.

Is there any mathematical way(as in using Permutation and Combination) to solve this problem or should I do a simulation to do it.

$\endgroup$
6
  • $\begingroup$ It feels more like a recurrence relation to me. You'd probably get to P's and C's eventually, just as a second step. $\endgroup$
    – markspace
    Jun 5, 2015 at 19:37
  • $\begingroup$ Can you give a little more explanation. $\endgroup$ Jun 5, 2015 at 19:41
  • $\begingroup$ and strings aren't even used at all, unless you need to produce them somehow. $\endgroup$
    – Dleep
    Jun 5, 2015 at 19:44
  • $\begingroup$ Are you saying that the only thing that matters is how many $a,b,c$ you have, i.e. if a bunch of strings are the same by permutations then they only count as 1 total string in the final count, instead of being counted individually? $\endgroup$ Jun 5, 2015 at 19:45
  • $\begingroup$ This isn't really about strings at all; it's about the number of integer solutions to $a+b+c=N$ with $a$ between min_a and max_a, etc. $\endgroup$ Jun 5, 2015 at 19:52

1 Answer 1

0
$\begingroup$

There may be a way to work out a final exact formula for this, but note that first of all you can assume that each min is 0 by subtracting the sum of mins from $N$, and subtracting each min from the corresponding max, so e.g. you can assume the count of $a$ is between $0$ and $max(a) - min(a)$, and so forth, and that the sum is $N - min(a) - min(b) - min(c)$.

Let $N_a$ be the count of $a$ and so forth for $b$ and $c$. If you choose $N_a$, then each valid choice of $N_b$ leads to one solution for $N_c$, which may either be in the valid range for count of $c$ or not. The choices of $N_b$ are between $0$ and $N - N_a$ but you must have the max possible value of $N_c$ is greater than or equal to $N - N_a - N_b$. So this gives you the minimum possible value for $N_b$, given $N_a$, and the maximum possible value of $N_b$ given $N_a$ is equal to the minimum of $N - N_a$ and the original maximum value for $N_b$. So this tells you how many choices you have for $N_b$ given $N_a$, such that you can find a valid assignment for $N_c$ to complete the total assignment. And the choice of $N_c$ is unique given the choices for $N_b$ and $N_c$. Thus, in $O(N)$ time you can just do a for loop over the values of $N_a$ and count the number of valid solutions in $O(1)$ time for each value of $N_a$, without need for further nested for loops. Of course, if it's possible to eliminate the need for looping over $N_b$ then it should be possible to similarly eliminate the need for originally looping over $N_a$ too, but I haven't worked through the messy details yet to come up with a final closed form formula.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .