Problem Statement
You are given a String S. The string can have up to 2500 characters.
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 int[] containing two elements: the optimal indices x and y. If there are multiple optimal choices, find the one with the smallest x. If there are still multiple optimal choices, find the one with the smallest y.
Definition
- Class:
- SubstringReversal
- Method:
- solve
- Parameters:
- String
- Returns:
- int[]
- Method signature:
- int[] solve(String S)
- (be sure your method is public)
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').
Examples
"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 }
Back to all problems