FastPrepFastPrep
Problem Brief

Count Num Ways 🍒

FULLTIMEOA
See Amazon online assessment and hiring insights

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 lexicographically smaller than the original string.

Note:

  1. 1. 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.
  2. 2. 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".

Function Description:

  1. 1. Complete the function countNumWays in the editor.
  2. 2. countNumWays has the following parameters:
    1. a. string s:the original string
    2. b. int k:the algorithm parameter

Returns:

int: the number of possible ways to perform the operation ensuring the given constraint

1Example 1

Input
s = "amazon", k = 3
Output
1
Explanation
Example 1 illustration
Consider all substrings of length k = 3. There are the possible ways to perform the given operation are showing in the above img:

2Example 2

Input
s = "ababa", k = 2
Output
2
Explanation
There are the possible ways for k = 2: (1) ababa --> baaba: unsuccessful, lexicographically greater thanthe original string. (2) ababa --> aabba: successfully, lexicographically smaller than the original string. (3) ababa --> abbaa: unsuccessfully, lexicographically greater. (4) ababa --> abaab: successfully, lexicographically smaller.

Constraints

Limits and guarantees your solution can rely on.

  1. 1. 2 <= |s| <= 106
  2. 2. 1 <= k <= min (|s|, 20)
public int countNumWays(String s, int k) {
  // write your code here
}
Input

s

"amazon"

k

3

Output

1

Sign in to submit your solution.