Let us define a transformation that, given a string S of letters 'a' and/or 'b', replaces some consecutive sequence "abb" in S by "baa".
For example, after applying such a transformation to the string "abbabb", both strings "baaabb" and "abbbaa" can be obtained.
Write a function:
class Solution { public String solution(String S); }
that, given a string S of length N, returns the alphabetically largest string that can be obtained by performing the above operation any number of times.
Examples:
1. Given S = "ababb", your function should return "baaaa".
"baaaa" is alphabetically the largest possible outcome and may be obtained from "ababb" by using two transformations:
"ababb" → "abbaa" → "baaaa"
2. Given S = "abbbabb", your function should return "babaaaa".
"babaaaa" may be obtained from "abbbabb" by using three transformations:
"abbbabb" → "abbbbaa" → "baabbaa" → "babaaaa"
3. Given S = "aaabab", your function should return "aaabab".
No operation can be performed on S since it contains no "abb" fragment.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- string S is made only of the characters 'a' and/or 'b'.
class Solution {
public String solution(String S) {
char[] A = S.toCharArray();
int i = 0;
while (i + 3 <= A.length) {
if (A[i] == 'a' && A[i + 1] == 'b' && A[i + 2] == 'b') {
A[i] = 'b';
A[i + 1] = 'a';
A[i + 2] = 'a';
i = Math.max(i - 2, 0);
} else
i++;
}
return new String(A);
}
}
class Solution {
public String solution(String S) {
char[] A = S.toCharArray();
int i = 0;
while (i + 3 <= A.length) {
if (A[i] == 'a' && A[i + 1] == 'b' && A[i + 2] == 'b') {
A[i] = 'b';
A[i + 1] = 'a';
A[i + 2] = 'a';
i = Math.max(i - 2, 0);
} else
i++;
}
return new String(A);
}
}
class Solution {
public String solution(String S) {
char[] A = S.toCharArray();
int i = 0;
while (i + 3 <= A.length) {
if (A[i] == 'a' && A[i + 1] == 'b' && A[i + 2] == 'b') {
A[i] = 'b';
A[i + 1] = 'a';
A[i + 2] = 'a';
i = Math.max(i - 2, 0);
} else
i++;
}
return new String(A);
}
}
The solution obtained perfect score.