Count Strings with At Most K Adjacent Equal

Problem

Count the strings of length n over 26 lowercase letters that have at most k positions i where the character at i equals the character at i + 1.

A string with exactly j adjacent equal pairs is determined by choosing those j positions among n - 1 gaps, then choosing 26 letters for the first position and 25 different letters after every gap. Sum over j from 0 to k.

Hint

Every gap either repeats the previous letter or changes to one of the other 25.

Test cases

case 1

in: [1,0]

expected: 26

case 2

in: [2,0]

expected: 650

case 3

in: [2,1]

expected: 676

case 4

in: [3,1]

expected: 17550

case 5

in: [5,2]

expected: 11878750

Starter codePython

def count_strings_at_most_k_adjacent_equal(n, k):
    # Your code here
    pass

5 test cases · run your code against them in the editor