FastPrep

Description

Solutions

Find Maximum Number of Strings

🔥 FULLTIME🤘 INTERN📚RELATED PROBLEMS

You are given 2 integers n and k. We have to find the maximum possible number of strings of size n such that the difference between 2 adjacent characters in the string is less than or equal to k. Given, all characters of the string should be smallcase alphabets.

The difference between 2 characters means the difference between their position in the alphabet list. For example, f - c = 3, b - a = 1.

Example 1:

Input:  n = 2, k = 3
Output: 170 
Explanation:
      
      For example, if we take the string "ab", the difference between a and b is 1. Thus this is a valid string.
      
      
      Similarly the strings "cd", "ce", "cf", "gi" are also valid.
      
      
      Like this there are 170 strings of length n = 2 that are fulfilling the condition.

Constraints:

1 <= n <= 10^6
1 <= k <= 25