FastPrep

Description

Solutions

TikTok Balanced Clips

🤘 INTERN📚RELATED PROBLEMS

TikTok creates random clips made up of lowercase English letters.

A clip is called "smooth" if the difference between any two letters next to each other is not bigger than a number called diff.

The difference between two letters, x and y, is how far apart they are in the alphabet. For example, the difference between 'a' and 'z' is 25, and between 'f' and 'c' is 3.

i.e. If diff = 3, then the clip "ac" is smooth because the difference between 'a' and 'c' is 2, which is less than or equal to 3. However, the clip "az" is not smooth because the difference between 'a' and 'z' is 25, which is greater than 3.

You are given two numbers: clipLength (the number of letters in the clip) and diff (the maximum allowed difference between two letters next to each other). Your job is to find how many smooth clips of length clipLength can be made. Since the number could be very large, give the answer as the result modulo 10^9 + 7.

Function Description

Complete the function countBalancedClips in the editor.

countBalancedClips has the following parameters:

1. int clipLength: the length of the clips
2. int diff: the maximum allowed difference between adjacent characters

Returns

int: the total number of balanced clips of the given clipLength, modulo (10^9 + 7)

Example 1:

Input:  clipLength = 2, diff = 3
Output: 170 
Explanation:
      
      Consider the following strings of length 2:
      
      
        
          Produced Word
          Is Balanced?
          Remarks
        
        
          "ad"
          Yes
          Difference between 'a' and 'd' is 3 i.e ≤ 3
        
        
          "za"
          No
          Difference between 'z' and 'a' is 25 i.e > 3
        
        
          "zx"
          Yes
          Difference between 'z' and 'x' is 2 i.e ≤ 3
        
        
          "rk"
          No
          Difference between 'r' and 'k' is 7 i.e > 3
        
        
          "yy"
          Yes
          Difference between 'y' and 'y' is 0
        
      
      
      Other examples of smooth clips for diff = 3 include: "ab", "ac", "df", "zr", and "op".
      The total number of smooth clips of length 2 for diff = 3 is 170. So, the answer is 170.

Produced Word	Is Balanced?	Remarks
"ad"	Yes	Difference between 'a' and 'd' is 3 i.e ≤ 3
"za"	No	Difference between 'z' and 'a' is 25 i.e > 3
"zx"	Yes	Difference between 'z' and 'x' is 2 i.e ≤ 3
"rk"	No	Difference between 'r' and 'k' is 7 i.e > 3
"yy"	Yes	Difference between 'y' and 'y' is 0

Constraints:

2 ≤ clipLength ≤ 10^5
1 ≤ diff ≤ 25