#StackBounty: #string #math #combinatorics #fastest-code Average number of strings with Levenshtein distance up to 4

Bounty: 50

This is a version of this question which should not have such a straightforward solution and so should be more of an interesting coding challenge. It seems, for example, very likely there is no easy to find closed form solution, even though we have only increased the bound by one from the previous version. Having said that, you never know…

The Levenshtein distance between two strings is the minimum number of single character insertions, deletions, or substitutions to convert one string into the other one. Given a binary string $S$ of length $n$, we are a interested in the number of different strings of length $n$ which have distance at most $4$ from $S$.

For example, if $S = 0000$ there are four strings with Levenshtein distance exactly $3$ from $S$, six with distance exactly $2$, four with distance exactly $1$ and exactly one with distance $0$. This makes a total of $15$ distinct strings with distance at most $3$ from the string $0000$. The only string with distance exactly $4$ is $1111$.

For this task the input is a value of $n geq 4$. Your code must output the average number of binary strings of length $n$ which have Levenshtein distance at most $4$ from a uniform and randomly sampled string $S$. Your answer can be output in any standard way you choose but it must be exact.


  • n = 4. Average $16$.
  • n = 5. Average 31 $frac{11}{16}$.
  • n = 6. Average 61 $frac{21}{32}$.
  • n = 7. Average 116 $frac{7}{8}$.
  • n = 8. Average 214 $frac{43}{128}$.
  • n = 9. Average 378 $frac{49}{246}$.
  • n = 10. Average 640 $frac{301}{512}$.
  • n = 11. Average 1042 $frac{1}{16}$.
  • n = 12. Average 1631 $frac{1345}{2048}$.
  • n = 13. Average 2466 $frac{3909}{4096}$.
  • n = 14. Average 3614 $frac{563}{8192}$


Your score is the highest value of $n$ you can reach in less than a minute on my linux box. If two answers get the same value then the first posted (or amended) wins. The timing is for each value separately.

My CPU is an Intel(R) Xeon(R) CPU X5460.

Get this bounty!!!

HackerRank: Paint The Tiles


Nikita has a line of N tiles indexed from 0 to N−1. She wants to paint them to match a color configuration, C, which is comprised of 2 colors: Red(R) and Blue(B)

In one stroke, Nikita can paint 1 or more adjacent tiles a single color. After she finishes painting, each tile(i) should be painted color C(i).

It should be noted that it is not allowed to apply more than 1 stroke on a tile.

Given the required color configuration, find and print the minimum number of strokes required for Nikita to paint all N tiles.

Note: In a line of tiles, 2 tiles with the indices i and j are considered adjacent only if |ji|=1.

Input Format

The first line contains a single integer, N, denoting the number of tiles to be painted.
The second line contains a string, C, denoting the desired color configuration.

For each character C(i) in C:

  • If C(i)=“R”, it means the ith tile must be painted red.
  • If C(i)=“B”, it means the ith tile must be painted blue.


  • 1N1000
  • C(i){“R”, “B”}

Output Format

Print the minimum number of strokes required to paint all tiles in the desired color configuration.

Sample Input 0


Sample Output 0


Sample Input 1


Sample Output 1


Sample Input 2


Sample Output 2



Sample Case 0:

Nikita will paint all 5 consecutive tiles red in a single stroke:

Sample Case 1:

Nikita will need 3 strokes to paint all 5 tiles: