SwapTheString | Topcoder Archive

Problem Statement

You are given a string S of length N. You are also given an integer K. In each step, you are allowed to select an index i and swap the characters at indices i and i + K (such that i + K < N) in the string S. After the swap, the new formed string should be lexographically greater than the old string. You keep on performing such steps, as long as possible. You need to find the maximum number of steps that can be performed on the given string.

You are given integers A0, X, Y and N and a string P. Use the pseudocode below to generate the string S.

A[0] = A0 for i = 1 to N-1: 	A[i] = (A[i-1] * X + Y) modulo 1812447359 S = P for i = size(P) to N-1: 	S[i] = (char)(A[i] % 26 + 'a')

Definition

Class:: SwapTheString
Method:: findNumberOfSwaps
Parameters:: String, int, int, int, int, int
Returns:: long
Method signature:: long findNumberOfSwaps(String P, int A0, int X, int Y, int N, int K)
(be sure your method is public)

Constraints

The length of P will be between 0 and min(N, 100) (inclusive)
A0 will be between 0 and 1812447358 (inclusive)
X will be between 0 and 1812447358 (inclusive)
Y will be between 0 and 1812447358 (inclusive)
N will be between 1 and 200,000 (inclusive)
K will be between 1 and N (inclusive)
String P will only contain lowercase English letters ('a'-'z').

Examples

```
"cbexa"
```
```
0
```
```
0
```
```
0
```
```
5
```
```
2
```
```
Returns: 2
```
There are 2 possible swaps in string "cbexa" : "cbexa" -> "cxeba" (swapping characters at index 1 and 3) and then "cxeba" -> "excba" (swapping characters at index 0 and 2). Note that if the k would have been 1, more swaps would have been possible.
```
""
```
```
5
```
```
2
```
```
3
```
```
4
```
```
1
```
```
Returns: 3
```
The string here is "fndj". There are 3 swaps possible : "fndj" -> "fnjd", "fnjd" -> "nfjd" and "nfjd" -> "njfd". Note that there can be multiple ways to do these swaps.
```
"b"
```
```
1001
```
```
1001
```
```
1001
```
```
5
```
```
2
```
```
Returns: 3
```
The string is "banol". There are 3 swaps possible : "banol" -> "bonal", "bonal" -> "nobal" and "nobal" -> "nolab".
```
""
```
```
9999
```
```
50000
```
```
4797
```
```
6
```
```
3
```
```
Returns: 2
```
```
""
```
```
3435
```
```
1000000000
```
```
1812447358
```
```
7
```
```
2
```
```
Returns: 5
```

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.