Problem description
Given a string $\it{s}$, length $\it{l}$ and an integer $\it{b}$, calculate the number of strings of size $\it{l}$ which has exactly $\it{b}$ substrings which are lexicographically greater than the corresponding substring in $\it{s}$.
Here's an example to elaborate on the problem statement. Suppose the give string $\bf{s=bby}$ and we have $\bf{l = 3}$ and $\bf{b = 2}$, so now the string $\bf{cby}$ is not part of the the solution because although it comes latter in lexicographical order but here we have three substrings $\bf{(cby, cb, c)}$ which are lexicographically greater than the corresponding substrings $\bf{(bby, bb, b)}$ of $\bf{s}$ but the number of such substrings should be exactly equal to b. Another example is $\bf{acy}$ which has exactly 2 substrings $\bf{(c, cy)}$ which are greater than the corresponding substrings of $\bf{s}$. So, $\bf{acy}$ is part of the solution.
My attempt at solving it
Altough I am able to solve it for some smaller values of $\it{l}$ and $\it{b}$ by counting all posibilities but I am not able to come up with a recurrence relation.
Taking the same value for $\it{l}$ and $\it{b}$ as above, and let $\it{s}$ be a string of length 3. So now, if a string $\it{t}$ is part of the solution then we cannot have $\it{t_0}$ (lets denote $\it{i-th}$ character of a string $\it{x}$ with $\it{x_i}$) greater than $\it{s_0}$ because then we will have at least 3 substrings $\it{(t_0t_1t_2, t_0t_1, t_0)}$ greater than corresponding substrings of $\it{s}$ and we also cannot have both $\it{t_1}$ and $\it{t_2}$ greater than $\it{s_1}$ and $\it{s_2}$ respectively, because then we will also have a third substring $\it{t_1t_2}$ greater than $\it{s_1s_2}$.
So, lets take the example from above and look at the remaining cases.
$\bf{Case 1:}$ When $\it{t_0=s_0}$, now we cannot have $\it{t_1 > s_1}$ because then again we will have three substrings which are greater and we also cannot have $\it{t_1 < s_1}$ because then we can have at most one greater substring. We also cannot have $\it{t_1 = s_1}$ because then depending on the value of $\it{t_2}$ we will have either three or zero greater substrings.
So, this case produces zero possibilities for $\it{bby}$.
$\bf{Case 2:}$ When $\it{t_0 < s_0}$, now the solution is sum of total number of strings where $\it{t_1 = s_1}$ and $\it{t_2 > s_2}$ and strings where $\it{t_1 > s_1}$ and $\it{t_2 <= s_2}$.
So, this case produces $\it{1*1 + 1 * 24 * 25 = 601}$ possibilities for $\it{bby}$ which is the final answer.
So, now the problem is to come up with a recurrence relation to solve for any arbitrary value of the parameters.