KthStringAgain | Topcoder Archive

Problem Statement

You are given a String s of length m. We will now define a collection of exactly 2^m (not necessarily distinct) strings. The collection is generated by the following pseudocode:

start with an empty collection
for each subset X of the set {1,2,...,m}:
    take a new string t and initialize it to the given string s
    for i = 1,2,...,m:
        if X contains i:
            reverse the last i characters of t
    add the string t to the collection

You are also given a long k. Imagine that we sorted our entire collection lexicographically. Find and return the string that will appear k-th in the sorted collection. (Note that k is a 1-based index.)

Definition

Class:: KthStringAgain
Method:: getKth
Parameters:: String, long
Returns:: String
Method signature:: String getKth(String s, long k)
(be sure your method is public)

Constraints

s will consist only of lowercase English letters ('a'-'z').
The length of s will be between 1 and 50, inclusive.
k will be between 1 and 2^n, inclusive, where n is the length of s.

Examples

```
"xyz"
```
```
5
```
```
Returns: "yzx"
```
Pseudocode will generate the following strings: "xyz" for X = {} (empty set), "xyz" for X = {1}, "xzy" for X = {2}, "xzy" for X = {1, 2}, "zyx" for X = {3}, "zyx" for X = {1, 3}, "yzx" for X = {2, 3}, "yzx" for X = {1, 2, 3}. Sorted lexicographically collection: "xyz", "xyz", "xzy", "xzy", "yzx", "yzx", "zyx", "zyx". The 5th string is "yzx".
```
"abc"
```
```
1
```
```
Returns: "abc"
```
```
"abc"
```
```
8
```
```
Returns: "cba"
```
```
"topcoder"
```
```
58
```
```
Returns: "ooredcpt"
```

"aaaabcdeeeghhhhhiijjjkllmmooooqqrrrrssttuuvvvvvwyy"

38517901796974

Returns: "aaaacdeehhhijklmmqqrsttvvvvwyyvuusrrrooooljjihhgeb"

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.