No. of strings between 2 given strings in lexicographical order

Question

I have been given 2 strings namely A and B and I have to find the no. of strings lying between A and B where the inbetween lying strings must be formed only from the characters of A.

Another restriction is that each letter has to be used exactly once.

For example :

A->abc

B->ddd

Ans=5

From string abc, the strings obtained are acb, bac, bca, cab, cba, all of them are larger than abc, but smaller than ddd. So the answer is 5.

Also, it may be the case that a given character in the string may repeat any number of times.ie- the below case is also included in the problem statement.

A->abacaba

B->ubuduba

Ans=64

How do I find the no. of such strings ?

Answer 1

Let $S=\{\text{a},\ldots,\text{z}\}$ be our alphabet, $S^*$ the set of words over that alphabet, $\epsilon$ the empty word. First we solve the following problem

Given a map $f\colon S\to\Bbb N_0$, compute the number $N(f)$ of words $\xi\in S^*$ such that each $x\in S$ occurs exactly $f(x)$ times in $\xi$.

This is easy. One readily finds $$N(f)=\frac{(\sum_{x\in S}f(x))!}{\prod_{x\in S}f(x)!}.$$

Next, we use recursion (on the length of $\beta$) to solve the following task

Given a map $f\colon S\to\Bbb N_0$ and a word $\beta\in S^*$, compute the number $N(f,\beta)$ of words $\xi\in S^*$ such that $\xi<\beta$ and each $x\in S$ occurs exactly $f(x)$ times in $\xi$.

If $\beta=\epsilon$, then clearly $$N(f,\beta)=0.$$ Otherwise, write $\beta=b\beta'$ with $b\in S$, $\beta'\in S^*$. For $x\in S$ with $f(x)>0$ define $$f_x(t)=\begin{cases}f(t)-1&t=x\\f(t)&t\ne x\end{cases}.$$ Then one sees that $$ N(f,\beta)=\sum_{x<b,\atop f(x)>0} N(f_x)+\begin{cases}N(f_b,\beta')&f(b)>0\\0&f(b)=0\end{cases}.$$

---

Now finally

Given $\alpha,\beta\in S^*$, the number of words $\xi\in S^*$ such that $\alpha<\xi<\beta$ and each letter $x$ occurs in $\xi$ and in $\alpha$ with the same frequency $f(x)$, is $$N(f,\beta)-N(f,\alpha)-1. $$