### 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

0)

 `"BCDAF"`
`Returns: "ABCDF"`
 The example from the problem statement.
1)

 `"ABBA"`
`Returns: "AABB"`
2)

 `"ACAB"`
`Returns: "AACB"`
 Here, you cannot get "AABC". The best you can get is "AACB" by reversing prefixes of length 2 and 3.

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8713

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12046&pm=8713

andrewzta

#### Testers:

PabloGilberto , Olexiy , ivan_metelsky , ged

#### Problem categories:

Dynamic Programming, Math, String Manipulation