Find Maximum Number of Strings

Maximum Number of Adjacent-Difference Bounded Strings Medium · Topics · Company Tags · Hints

You are given two integers n and k. Your task is to compute the maximum number of strings of length n that can be formed under the following rules:

• Every character must be a lowercase English letter ('a' through 'z').
• For any two adjacent characters in the string, the absolute difference of their alphabetical indices must not exceed k.

The alphabetical index of a letter is its 1‑based position: 'a' = 1, 'b' = 2, …, 'z' = 26. The difference between two letters c1 and c2 is |pos(c1) - pos(c2)|. For instance, |pos('f') - pos('c')| = |6 - 3| = 3, and |pos('b') - pos('a')| = |2 - 1| = 1.

Return the total count modulo 10^9 + 7 (since the answer can be very large).

Example 1:

Input: n = 2, k = 3

Output: 170

Explanation: For length 2 with allowed adjacent difference ≤ 3, exactly 170 distinct strings over lowercase letters satisfy the condition.

Example 2:

Input: n = 1, k = 10

Output: 26

Explanation: A string of length 1 has no adjacent pairs, so every lowercase letter is valid, giving 26 possible strings.

Example 3:

Input: n = 3, k = 1

Output: 98

Constraints:

• 1 <= n <= 1,000,000
• 1 <= k <= 25
• The result must be returned modulo 1,000,000,007.