TopCoder problem "ReversingPrefixes" used in TCHS08 Finals (Division I Level Two)



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

Writer:

andrewzta

Testers:

PabloGilberto , Olexiy , ivan_metelsky , ged

Problem categories:

Dynamic Programming, Math, String Manipulation