Count Num Ways 🍒

Amazon is working on a new hashing approach that takes in the original string and a seed number.

Engineers decided that the seed can be generated from the same input string by counting the number of times a reverse of a substring of length k makes the new string lexicographically smaller. You are deployed with the task of developing a service that takes in a string s and an integer k, and returns the number of ways to reverse any substring of length k such that the resulting string is strictly lexicographically smaller than the original string.

Note:

• A substring is a contiguous sequence of characters within a string. For example, the string "zon" is a substring of "amazon", "zone", etc., but is not a substring of "zoin", "zozo", etc.
• A string a is lexicographically smaller than string b if a[i] < b[i] at the first index where a and b differ. For example, "amazon" is lexicographically smaller than "amozan".
• Reversing a substring that produces a string equal to the original (for example, a palindromic substring) is not counted, since the result must be strictly smaller than the original string.

Function Description:

• Complete the function countNumWays in the editor.
• countNumWays has the following parameters:
  • String s: the original string
  • int k: the algorithm parameter

Returns:

int: the number of possible ways to perform the operation such that the resulting string is strictly lexicographically smaller than the original string.