SubstringReversal
TCO14 Round 2C · 2014-03-26 · by misof
Problem Statement
You are given a
You have to reverse exactly one substring of S. Formally, you have to choose two 0-based indices {x,y} such that x <= y, and then you have to reverse the order of the letters with indices x through y, inclusive. That is, S[x]S[x+1]...S[y] becomes S[y]...S[x+1]S[x].
For example, if S="abcdefg", you can choose the indices {2,5} to obtain "abfedcg", the indices {0,1} to obtain "bacdefg", or the indices {3,3} to obtain "abcdefg". (In the last example, only one letter was selected, so the string did not change.)
Your goal is to produce the lexicographically smallest string possible. Return a
Notes
- Given two strings A and B of equal length, we say that A is lexicographically smaller than B if A has a smaller character than B at the first position where they differ.
Constraints
- S will contain between 1 and 2500 elements, inclusive.
- Each character of S will be a lowercase letter ('a'-'z').
"abdc"
Returns: {2, 3 }
Reverse "dc" to "cd".
"aabbcc"
Returns: {0, 0 }
Nothing to reverse here, you cannot produce a lexicographically smaller string.
"misof"
Returns: {0, 4 }
Reverse the entire string.
"ivan"
Returns: {0, 2 }
Reverse "iva" to bring 'a' to the beginning.
"thisseemstobeaneasyproblem"
Returns: {0, 13 }
Submissions are judged against all 273 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SubstringReversal with a public method vector<int> solve(string S) · 273 test cases · 2 s / 256 MB per case