Amazon | OA | Robot With Strings
Anonymous User
1435
Jun 18, 2022
Jun 18, 2022
There are three robots named Ray, Ben, and Kevin. Initially Ray has a string S of length N, while the other two robots have empty strings. We can make either of the following moves:
- Move 1: Remove the first character from Ray's string and append it to Ben's string.
- Move 2: Remove the last character from Ben's string and append it to Kevin's string.
You must perform either fo the two moves mentioned above in such a way that the strings left with Ray and Ben are empty and the string left with Kevin is lexicographically smallest string that Kevin has after completing this activity.
Input specs:
input1: integer denoting the length N of the string S
input2: A string S which belongs to Ray and contains all lowercase characters.
Output specs:
A string value denoting the string left with Kevin which is lexicographically smallest.
Example1:
Input: [3, dad]
Output: add
Example2:
input: [3, cba]
output: abc
/**
Move 1: Remove the first char from R and append it to B.
Move 2: Remove the last char from B and append it to K.
*/
private String solve(String R, String B, String K){
String newB, newR, newK;
if(R.length() == 0) {
if(B.length() > 0){
StringBuilder sb = new StringBuilder(K);
for(int i = B.length()-1; i >= 0; i--) sb.append(B.charAt(i));
return sb.toString();
}
return K;
}
else if(B.length() == 0) {
newB = B + R.charAt(0);
newR = R.substring(1);
return solve(newR, newB, K);
}
else {
newB = B + R.charAt(0);
newR = R.substring(1);
String move1 = solve(newR, newB, K);
newK = K + B.charAt(B.length()-1);
newB = B.substring(0, B.length()-1);
String move2 = solve(R, newB, newK);
return move1.compareTo(move2) <= 0 ? move1 : move2;
}
}Comments (12)
