How should I practice Count Num Ways 🍒?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Amazon online assessment problems in FastPrep.

Is Count Num Ways 🍒 associated with Amazon?

FastPrep tags this as a Amazon online assessment coding practice problem when the problem catalog has that company and stage context.

Problem · String

Count Num Ways 🍒

Learn this problem

● Medium

AmazonFULLTIMEOA

See Amazon hiring insights

Problem statement

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

countNumWays(s: String, k: int) → int

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.

Examples

Example 1

s = "amazon"k = 3return = 1

Consider all substrings of length k = 3. The possible ways to perform the operation are: (1) Reverse "ama" -> "amazon": unsuccessful (lexicographically equal). (2) Reverse "maz" -> "azamon": unsuccessful (lexicographically greater). (3) Reverse "azo" -> "amozan": unsuccessful (lexicographically greater). (4) Reverse "zon" -> "amanoz": successful (lexicographically smaller). Only one way is possible, so return 1.

Example 2

s = "ababa"k = 2return = 2

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

2 <= |s| <= 10⁶
1 <= k <= min(|s|, 20)
s consists of lowercase English letters.