RingLex | Topcoder Archive

Problem Statement

Hero has an infinite periodic string t. You are given the String s that is the period of Hero's string. For example, if s = "abc", Hero's actual string is t = "abcabcabcabc..." Let n be the length of string s. Hero is now going to use the infinite string t to generate a new n-character string by doing the following steps:

He will choose an offset: a non-negative integer x.
He will choose the length of a step: a prime number p that is less than n.
The new string will consists of the first n characters we can read in the string t if we start at the index x and after each character we move p positions to the right.

Formally, Hero's new string will consist of the following characters, in order: t[x], t[x + p], t[x + 2*p], ..., t[x + (n-1)*p]. Find and return the lexicographically smallest string Hero can produce.

Definition

Class:: RingLex
Method:: getmin
Parameters:: String
Returns:: String
Method signature:: String getmin(String s)
(be sure your method is public)

Notes

Given two distinct strings of the same length, the lexicographically smaller one is the one that has a smaller character at the first position where they differ.
A positive integer p is a prime if it has exactly two distinct divisors: 1 and p. Note that the number 1 is not a prime.

Constraints

s will contain between 3 and 50 characters, inclusive.
Each character in s will be between 'a' and 'z', inclusive.

Examples

```
"cba"
```
```
Returns: "abc"
```
Hero should choose the offset x=2 and the step p=2. The resulting string is t[2]+t[4]+t[6] = 'a'+'b'+'c' = "abc".
```
"acb"
```
```
Returns: "abc"
```
Here, Hero should choose x=0 and p=2.
```
"abacaba"
```
```
Returns: "aaaabcb"
```
```
"aaabb"
```
```
Returns: "aabab"
```
```
"azzzabbb"
```
```
Returns: "abazabaz"
```
Note that Hero cannot choose x=0 and p=4, because 4 is not a prime number.
```
"abbaac"
```
```
Returns: "aaaaaa"
```
```
"fsdifyhsoe"
```
```
Returns: "dehifsfsoy"
```

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.