Looking at the explanations, it seems that if we think of inserting alphabets arbitrarily $K$ times and consider the positions of each character in $S$ as fixed in a string of length $N+K$, it works well. Thinking that way, we just need to consider how to insert $K$ characters in a string of length $N+K$.
Let’s think using Example Input 1.
- S = “oof”
- N = len(“oof”) = 3
- K = 5
For example, place ‘o’ at position 1, ‘o’ at position 3, and ‘f’ at position 5. Also, when looking at the string of length $N+K$ from the beginning, these positions are where “oof” first appears (condition 1). At this time, we can insert 25 types of alphabets other than ‘o’ at position 0. Conversely, inserting ‘o’ at position 0 does not satisfy condition 1, so it’s not allowed. Similarly, we can insert 25 types of alphabets other than ‘o’ at position 2. Also, we can insert 25 types of alphabets other than ‘f’ at position 4. For positions 6 and 7, there are no particular constraints, so we can insert 26 types of alphabets.
In summary, when the position $j$ of ‘f’ moves from $N-1 … N+K-1$, the number of combinations where two ‘o’s can be placed is ${}_j C _{N-1}$.
Also, there are $j - (N-1)$ positions to insert 25 types of alphabets, and $(N+K-1)$ positions to insert 26 types of alphabets.
That is, the answer is $\sum_{j=N-1}^{N+K-1} {}_j C _{N-1} \cdot 25^{j-(N-1)} \cdot 26^{(N+K-1)-j}$.