ReversingPrefixes | Topcoder Archive

Problem Statement

You are given a String s. In increasing order, consider each integer i between 1 and the length of s, inclusive. For each value of i, you can choose whether or not to perform the following operation: Take the prefix of length i of the current string and reverse it. Your ultimate goal is to end up with the alphabetically earliest string possible.

For example, if s = "BCDAF", you should reverse the prefix of length 3 to get "DCBAF", and then reverse the prefix of length 4 to get "ABCDF".

Return the alphabetically earliest string possible.

Definition

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

Notes

A String A comes before a String B alphabetically if A is a proper prefix of B, or if A has a smaller character at the first position where the strings differ.

Constraints

s will contain between 1 and 50 characters, inclusive.
s will contain only uppercase letters ('A'-'Z').

Examples

```
"BCDAF"
```
```
Returns: "ABCDF"
```
The example from the problem statement.
```
"ABBA"
```
```
Returns: "AABB"
```
```
"ACAB"
```
```
Returns: "AACB"
```
Here, you cannot get "AABC". The best you can get is "AACB" by reversing prefixes of length 2 and 3.

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.