SubstringReversal2 | Topcoder Archive

Problem Statement

You are given a string S of length N. Consider an even-sized subset of {1, 2,..., N}. Say the subset is { p₁, p₂,.., p_2k} such that p₁ < p₂ < ... < p_2k. Now we'll construct a new string from S as follows : reverse the substring from p(2i-1) to p(2i) (inclusive) for each i from 1 to k. Now consider the multiset of strings which can be built in this method by choosing all even-sized subset of {1, 2,..., N}. You have to find the K^th lexicographical string that can be built. It is guaranteed that such a string exists.

Say N = 8, and let's choose a subset, say {1, 3, 6, 8}. Then we reverse the substrings S[1 : 3] and S[6 : 8]. (1-based indexing)

For example, for the string "abcd", the following strings can be built :
abcd
abdc
acbd
adcb
bacd
badc
cbad
dcba
The 3^rd lexicographical string is acbd.

Definition

Class:: SubstringReversal2
Method:: solve
Parameters:: String, long
Returns:: String
Method signature:: String solve(String S, long K)
(be sure your method is public)

Notes

Given two strings A and B of equal length, we say that A is lexicographically smaller than B if A has a smaller character than B at the first position where they differ.
It's guaranteed that such a string will exist.

Constraints

S will contain between 1 and 200 elements, 'a'-'z'.
K will be between 1 and 1018.

Examples

```
"abcd"
```
```
6
```
```
Returns: "badc"
```
For the string "abcd", the strings generated are "abcd", "abdc", "acbd", "adcb", "bacd", "badc", "cbad" and "dcba". Among them the 6th lexicographic string is "badc".
```
"topcoder"
```
```
40
```
```
Returns: "otpdocre"
```
```
"aabc"
```
```
2
```
```
Returns: "aabc"
```
For the string "aabc", the strings generated are "aabc", "aabc", "aacb", "aacb", "abac", "acba", "baac" and "cbaa". Among them the 2nd lexicographic string is "aabc".

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.