What is the meaning of the first constraint "numbers of their digits are the same"? It seems redundant given the multiset condition.

Let $$$next(x)$$$ be the number $$$y$$$ whose digits are the next lexicographically-ordered permutation of digits of $$$x$$$. In case $$$y$$$ doesn't exist, let $$$next(x)$$$ be $$$\infty$$$.

Let $$$prev(y)$$$ be the number $$$x$$$ whose digits are the previous lexicographically-ordered permutation of digits of $$$y$$$. In case $$$x$$$ doesn't exist or $$$x$$$ contains leading zeros, let $$$prev(y)$$$ be $$$-\infty$$$.

It is equivalent to count the pairs of $$$(x, y)$$$ such that $$$next(x) = y$$$ and $$$prev(x) < l \leq x < y \leq r < next(y)$$$. Obviously, the answer is twice its number.

Let's take a look at the algorithm (in linear time complexity) to find the next permutation of an array $$$a_1, a_2, \ldots, a_m$$$:

• First, we need to find the rightmost $$$i$$$ such that $$$i < m$$$, $$$a_i < a_{i + 1}$$$. If no such $$$i$$$, no permutation is greater than the array, since $$$a_1, a_2, \ldots, a_m$$$ are in non-increasing order.
• Then, we need to find the rightmost $$$j$$$ such that $$$i < j$$$, $$$a_i < a_j$$$. It always exists since $$$a_i < a_{i + 1}$$$.
• Finally, we need to swap $$$a_i$$$ and $$$a_j$$$, and then reverse the elements $$$a_{i + 1}, a_{i + 2}, \ldots, a_m$$$.

For example, $$$12\color{red}{3}\color{blue}{4} \to 12\color{blue}{4}\color{red}{3}$$$, $$$\color{red}{1}\color{blue}{2}11 \to \color{blue}{2}11\color{red}{1}$$$ and $$$\color{red}{5}9866\color{blue}{6}5 \to \color{blue}{6}5\color{red}{5}6689$$$.

When we care about at most $$$4$$$ adjacent permutations of digits, those digits that are useful for the algorithm of finding next permutation must be in the lowest $$$3$$$ non-increasing blocks, for instance, $$$\color{red}{7}\color{green}{9777655532210}\color{blue}{1}, \color{red}{7}\color{blue}{97776555322110}, 9011223555\color{red}{6}\color{blue}{7777}, 9011223555\color{red}{76}\color{blue}{777}$$$. But actually, do we really need to care about maybe a huge number of situtations? No.

In most cases, the difference between integers corresponding to $$$2$$$ adjacent permutations is quite small, such as $$$(6556689, 6556698)$$$ and $$$(797776555322101, 797776555322110)$$$. It is because the lowest non-decreasing block is long enough, and we can only consider them when finding the next permutation.

The case that the difference between two adjacent similar integers $$$x, y$$$ is large is when the lower integer has a long non-increasing block. But in that case, the next similar integer $$$z$$$ usually comes with a fairly small difference of $$$(z - y)$$$.

It inspires that, in most cases, we can enumerate $$$(prev(x), x)$$$ or $$$(y, next(y))$$$, such that the difference of those two is small enough. The reason we only enumerate these two kinds but $$$(x, y)$$$ is that no matter in which of those two cases, we know $$$x$$$ or $$$y$$$ is close to $$$l$$$ or $$$r$$$.

In case that $$$prev(x) = -\infty$$$ and $$$next(y) = \infty$$$, we can conclude $$$12 \leq x < y \leq 98$$$, since $$$x$$$ must have at least two types of digits, and thus the number of all possible permutations of its digits is no less than its length. Since the difference is small, this situation can be enumerated by the above method, so we can avoid discussing it.

In case that $$$prev(x) = -\infty$$$, the digits of $$$x$$$ is in non-decreasing order, which implies the difference $$$(prev(y) - y)$$$ may be considerable. So as for $$$next(y) = \infty$$$.

Let's assume that we have handled all the cases with differences less than $$$10^3$$$. What are the rest cases? You may observe that the rest case is only like $$$(677777, 767777)$$$ and $$$(676666, 667666)$$$. Why? Because if the lowest $$$3$$$ digits are not the same, it will form many permutations and be enumerated in the above. Hence, we can enumerate the lowest digits in the form of $$$(p q q \ldots q, q p q \ldots q)$$$, $$$(p q p \ldots p, q p p \ldots p)$$$, and determine if they could form an interval that covers $$$l$$$ or $$$r$$$.

In summary:

• For covering most cases, we enumerate the numbers that are close to the endpoints of $$$[l, r]$$$ and forcibly check if they can be included in the answer.
• For covering the rest cases, we enumerate the possible suffix digits of $$$x$$$ or $$$y$$$ (i.e. $$$p$$$, $$$q$$$ and the length of the lowest same digits), and forcibly check again.

Time complexity: $$$\mathcal{O}(D^3 L + D^2 L^2)$$$, where $$$D = 10$$$ is the number of possible digits, $$$L = 15$$$ is the maximal length of a number.