Tasks Details
medium
Find the alphabetically largest string that can be obtained by performing some substitutions.
Task Score
100%
Correctness
100%
Performance
100%
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'.
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Java 21
Time spent on task 2 minutes
Notes
not defined yet
Code: 15:01:43 UTC,
java,
autosave
class Solution {
public String solution(String S) {
// A - true, B - false
boolean[] encoded = encode(S);
for (int i = encoded.length-3; i >= 0; i--) {
// System.out.println("len: "+encoded.length+", i: "+i);
if (encoded[i] && !encoded[i+1] && !encoded[i+2]) {
// do flip
encoded[i] = false;
encoded[i+1] = true;
encoded[i+2] = true;
// check if we didn't create new valid pattern behind by the flip
if (i+3 < encoded.length && !encoded[i+3] && !encoded[i+4])
i = i+3;
}
// printEncoded(encoded);
}
return decode(encoded);
}
public void printEncoded(boolean[] encoded) {
for (int i = 0; i < encoded.length; i++)
if (encoded[i])
System.out.print("a");
else
System.out.print("b");
System.out.println("");
}
public boolean[] encode(String s) {
// A - true, B - false
boolean[] encoded = new boolean[s.length()];
for (int i = 0; i < s.length(); i++)
if (s.charAt(i) == 'a')
encoded[i] = true;
return encoded;
}
public String decode(boolean[] s) {
// A - true, B - false
char[] text = new char[s.length];
for (int i = 0; i < s.length; i++)
if (s[i])
text[i] = 'a';
else
text[i] = 'b';
return new String(text);
}
}
Code: 15:01:55 UTC,
java,
verify,
result: Passed
class Solution {
public String solution(String S) {
// A - true, B - false
boolean[] encoded = encode(S);
for (int i = encoded.length-3; i >= 0; i--) {
// System.out.println("len: "+encoded.length+", i: "+i);
if (encoded[i] && !encoded[i+1] && !encoded[i+2]) {
// do flip
encoded[i] = false;
encoded[i+1] = true;
encoded[i+2] = true;
// check if we didn't create new valid pattern behind by the flip
if (i+3 < encoded.length && !encoded[i+3] && !encoded[i+4])
i = i+3;
}
// printEncoded(encoded);
}
return decode(encoded);
}
public void printEncoded(boolean[] encoded) {
for (int i = 0; i < encoded.length; i++)
if (encoded[i])
System.out.print("a");
else
System.out.print("b");
System.out.println("");
}
public boolean[] encode(String s) {
// A - true, B - false
boolean[] encoded = new boolean[s.length()];
for (int i = 0; i < s.length(); i++)
if (s.charAt(i) == 'a')
encoded[i] = true;
return encoded;
}
public String decode(boolean[] s) {
// A - true, B - false
char[] text = new char[s.length];
for (int i = 0; i < s.length; i++)
if (s[i])
text[i] = 'a';
else
text[i] = 'b';
return new String(text);
}
}
Analysis
expand all
User tests
1.
0.008 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 6 at Solution.solution(Solution.java:16) at Exec.run(exec.java:48) at Exec.main(exec.java:34)
1.
0.004 s
OK
function result: 'baa'
function result: 'baa'
User test case 1:
['abbbbb']
User test case 2:
['abb']
Code: 15:02:13 UTC,
java,
autosave
class Solution {
public String solution(String S) {
// A - true, B - false
boolean[] encoded = encode(S);
for (int i = encoded.length-3; i >= 0; i--) {
System.out.println("len: "+encoded.length+", i: "+i);
if (encoded[i] && !encoded[i+1] && !encoded[i+2]) {
// do flip
encoded[i] = false;
encoded[i+1] = true;
encoded[i+2] = true;
// check if we didn't create new valid pattern behind by the flip
if (i+3 < encoded.length && !encoded[i+3] && !encoded[i+4])
i = i+3;
}
printEncoded(encoded);
}
return decode(encoded);
}
public void printEncoded(boolean[] encoded) {
for (int i = 0; i < encoded.length; i++)
if (encoded[i])
System.out.print("a");
else
System.out.print("b");
System.out.println("");
}
public boolean[] encode(String s) {
// A - true, B - false
boolean[] encoded = new boolean[s.length()];
for (int i = 0; i < s.length(); i++)
if (s.charAt(i) == 'a')
encoded[i] = true;
return encoded;
}
public String decode(boolean[] s) {
// A - true, B - false
char[] text = new char[s.length];
for (int i = 0; i < s.length; i++)
if (s[i])
text[i] = 'a';
else
text[i] = 'b';
return new String(text);
}
}
Code: 15:02:17 UTC,
java,
verify,
result: Passed
class Solution {
public String solution(String S) {
// A - true, B - false
boolean[] encoded = encode(S);
for (int i = encoded.length-3; i >= 0; i--) {
System.out.println("len: "+encoded.length+", i: "+i);
if (encoded[i] && !encoded[i+1] && !encoded[i+2]) {
// do flip
encoded[i] = false;
encoded[i+1] = true;
encoded[i+2] = true;
// check if we didn't create new valid pattern behind by the flip
if (i+3 < encoded.length && !encoded[i+3] && !encoded[i+4])
i = i+3;
}
printEncoded(encoded);
}
return decode(encoded);
}
public void printEncoded(boolean[] encoded) {
for (int i = 0; i < encoded.length; i++)
if (encoded[i])
System.out.print("a");
else
System.out.print("b");
System.out.println("");
}
public boolean[] encode(String s) {
// A - true, B - false
boolean[] encoded = new boolean[s.length()];
for (int i = 0; i < s.length(); i++)
if (s.charAt(i) == 'a')
encoded[i] = true;
return encoded;
}
public String decode(boolean[] s) {
// A - true, B - false
char[] text = new char[s.length];
for (int i = 0; i < s.length; i++)
if (s[i])
text[i] = 'a';
else
text[i] = 'b';
return new String(text);
}
}
Analysis
expand all
Example tests
1.
0.004 s
OK
stdout:
len: 5, i: 2 abbaa len: 5, i: 1 abbaa len: 5, i: 0 baaaa
1.
0.004 s
OK
stdout:
len: 7, i: 4 abbbbaa len: 7, i: 3 abbbbaa len: 7, i: 2 abbbbaa len: 7, i: 1 abbbbaa len: 7, i: 0 baabbaa len: 7, i: 2 babaaaa len: 7, i: 1 babaaaa len: 7, i: 0 babaaaa
1.
0.008 s
OK
stdout:
len: 6, i: 3 aaabab len: 6, i: 2 aaabab len: 6, i: 1 aaabab len: 6, i: 0 aaabab
expand all
User tests
1.
0.004 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 6 at Solution.solution(Solution.java:16) at Exec.run(exec.java:48) at Exec.main(exec.java:34)stdout:
len: 6, i: 3 abbbbb len: 6, i: 2 abbbbb len: 6, i: 1 abbbbb len: 6, i: 0 baabbb len: 6, i: 2
1.
0.004 s
OK
function result: 'baa'
function result: 'baa'
stdout:
len: 3, i: 0 baa
User test case 1:
['abbbbb']
User test case 2:
['abb']
Code: 15:02:50 UTC,
java,
autosave
class Solution {
public String solution(String S) {
// A - true, B - false
boolean[] encoded = encode(S);
for (int i = encoded.length-3; i >= 0; i--) {
System.out.println("len: "+encoded.length+", i: "+i);
if (encoded[i] && !encoded[i+1] && !encoded[i+2]) {
// do flip
encoded[i] = false;
encoded[i+1] = true;
encoded[i+2] = true;
// check if we didn't create new valid pattern behind by the flip
if (i+4 < encoded.length && !encoded[i+3] && !encoded[i+4])
i = i+3;
}
printEncoded(encoded);
}
return decode(encoded);
}
public void printEncoded(boolean[] encoded) {
for (int i = 0; i < encoded.length; i++)
if (encoded[i])
System.out.print("a");
else
System.out.print("b");
System.out.println("");
}
public boolean[] encode(String s) {
// A - true, B - false
boolean[] encoded = new boolean[s.length()];
for (int i = 0; i < s.length(); i++)
if (s.charAt(i) == 'a')
encoded[i] = true;
return encoded;
}
public String decode(boolean[] s) {
// A - true, B - false
char[] text = new char[s.length];
for (int i = 0; i < s.length; i++)
if (s[i])
text[i] = 'a';
else
text[i] = 'b';
return new String(text);
}
}
Code: 15:02:51 UTC,
java,
verify,
result: Passed
class Solution {
public String solution(String S) {
// A - true, B - false
boolean[] encoded = encode(S);
for (int i = encoded.length-3; i >= 0; i--) {
System.out.println("len: "+encoded.length+", i: "+i);
if (encoded[i] && !encoded[i+1] && !encoded[i+2]) {
// do flip
encoded[i] = false;
encoded[i+1] = true;
encoded[i+2] = true;
// check if we didn't create new valid pattern behind by the flip
if (i+4 < encoded.length && !encoded[i+3] && !encoded[i+4])
i = i+3;
}
printEncoded(encoded);
}
return decode(encoded);
}
public void printEncoded(boolean[] encoded) {
for (int i = 0; i < encoded.length; i++)
if (encoded[i])
System.out.print("a");
else
System.out.print("b");
System.out.println("");
}
public boolean[] encode(String s) {
// A - true, B - false
boolean[] encoded = new boolean[s.length()];
for (int i = 0; i < s.length(); i++)
if (s.charAt(i) == 'a')
encoded[i] = true;
return encoded;
}
public String decode(boolean[] s) {
// A - true, B - false
char[] text = new char[s.length];
for (int i = 0; i < s.length; i++)
if (s[i])
text[i] = 'a';
else
text[i] = 'b';
return new String(text);
}
}
Analysis
expand all
Example tests
1.
0.012 s
OK
stdout:
len: 5, i: 2 abbaa len: 5, i: 1 abbaa len: 5, i: 0 baaaa
1.
0.012 s
OK
stdout:
len: 7, i: 4 abbbbaa len: 7, i: 3 abbbbaa len: 7, i: 2 abbbbaa len: 7, i: 1 abbbbaa len: 7, i: 0 baabbaa len: 7, i: 2 babaaaa len: 7, i: 1 babaaaa len: 7, i: 0 babaaaa
1.
0.012 s
OK
stdout:
len: 6, i: 3 aaabab len: 6, i: 2 aaabab len: 6, i: 1 aaabab len: 6, i: 0 aaabab
expand all
User tests
1.
0.012 s
OK
function result: 'babaab'
function result: 'babaab'
stdout:
len: 6, i: 3 abbbbb len: 6, i: 2 abbbbb len: 6, i: 1 abbbbb len: 6, i: 0 baabbb len: 6, i: 2 babaab len: 6, i: 1 babaab len: 6, i: 0 babaab
1.
0.008 s
OK
function result: 'baa'
function result: 'baa'
stdout:
len: 3, i: 0 baa
User test case 1:
['abbbbb']
User test case 2:
['abb']
Code: 15:03:16 UTC,
java,
verify,
result: Passed
class Solution {
public String solution(String S) {
// A - true, B - false
boolean[] encoded = encode(S);
for (int i = encoded.length-3; i >= 0; i--) {
// System.out.println("len: "+encoded.length+", i: "+i);
if (encoded[i] && !encoded[i+1] && !encoded[i+2]) {
// do flip
encoded[i] = false;
encoded[i+1] = true;
encoded[i+2] = true;
// check if we didn't create new valid pattern behind by the flip
if (i+4 < encoded.length && !encoded[i+3] && !encoded[i+4])
i = i+3;
}
// printEncoded(encoded);
}
return decode(encoded);
}
public void printEncoded(boolean[] encoded) {
for (int i = 0; i < encoded.length; i++)
if (encoded[i])
System.out.print("a");
else
System.out.print("b");
System.out.println("");
}
public boolean[] encode(String s) {
// A - true, B - false
boolean[] encoded = new boolean[s.length()];
for (int i = 0; i < s.length(); i++)
if (s.charAt(i) == 'a')
encoded[i] = true;
return encoded;
}
public String decode(boolean[] s) {
// A - true, B - false
char[] text = new char[s.length];
for (int i = 0; i < s.length; i++)
if (s[i])
text[i] = 'a';
else
text[i] = 'b';
return new String(text);
}
}
Analysis
User test case 1:
['abbbbb']
User test case 2:
['abb']
Code: 15:03:25 UTC,
java,
verify,
result: Passed
class Solution {
public String solution(String S) {
// A - true, B - false
boolean[] encoded = encode(S);
for (int i = encoded.length-3; i >= 0; i--) {
// System.out.println("len: "+encoded.length+", i: "+i);
if (encoded[i] && !encoded[i+1] && !encoded[i+2]) {
// do flip
encoded[i] = false;
encoded[i+1] = true;
encoded[i+2] = true;
// check if we didn't create new valid pattern behind by the flip
if (i+4 < encoded.length && !encoded[i+3] && !encoded[i+4])
i = i+3;
}
// printEncoded(encoded);
}
return decode(encoded);
}
public void printEncoded(boolean[] encoded) {
for (int i = 0; i < encoded.length; i++)
if (encoded[i])
System.out.print("a");
else
System.out.print("b");
System.out.println("");
}
public boolean[] encode(String s) {
// A - true, B - false
boolean[] encoded = new boolean[s.length()];
for (int i = 0; i < s.length(); i++)
if (s.charAt(i) == 'a')
encoded[i] = true;
return encoded;
}
public String decode(boolean[] s) {
// A - true, B - false
char[] text = new char[s.length];
for (int i = 0; i < s.length; i++)
if (s[i])
text[i] = 'a';
else
text[i] = 'b';
return new String(text);
}
}
Analysis
User test case 1:
['abbbbb']
User test case 2:
['abb']
Code: 15:03:31 UTC,
java,
final,
score:
100
class Solution {
public String solution(String S) {
// A - true, B - false
boolean[] encoded = encode(S);
for (int i = encoded.length-3; i >= 0; i--) {
// System.out.println("len: "+encoded.length+", i: "+i);
if (encoded[i] && !encoded[i+1] && !encoded[i+2]) {
// do flip
encoded[i] = false;
encoded[i+1] = true;
encoded[i+2] = true;
// check if we didn't create new valid pattern behind by the flip
if (i+4 < encoded.length && !encoded[i+3] && !encoded[i+4])
i = i+3;
}
// printEncoded(encoded);
}
return decode(encoded);
}
public void printEncoded(boolean[] encoded) {
for (int i = 0; i < encoded.length; i++)
if (encoded[i])
System.out.print("a");
else
System.out.print("b");
System.out.println("");
}
public boolean[] encode(String s) {
// A - true, B - false
boolean[] encoded = new boolean[s.length()];
for (int i = 0; i < s.length(); i++)
if (s.charAt(i) == 'a')
encoded[i] = true;
return encoded;
}
public String decode(boolean[] s) {
// A - true, B - false
char[] text = new char[s.length];
for (int i = 0; i < s.length; i++)
if (s[i])
text[i] = 'a';
else
text[i] = 'b';
return new String(text);
}
}Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N)
expand all
Correctness tests
1.
0.004 s
OK
2.
0.004 s
OK
3.
0.004 s
OK
4.
0.004 s
OK
5.
0.004 s
OK
1.
0.004 s
OK
2.
0.004 s
OK
1.
0.004 s
OK
2.
0.008 s
OK
3.
0.004 s
OK
4.
0.004 s
OK
5.
0.008 s
OK
1.
0.004 s
OK
2.
0.004 s
OK
3.
0.004 s
OK
4.
0.008 s
OK
5.
0.004 s
OK
1.
0.004 s
OK
2.
0.004 s
OK
3.
0.004 s
OK
4.
0.008 s
OK
5.
0.004 s
OK
6.
0.004 s
OK
1.
0.004 s
OK
2.
0.008 s
OK
3.
0.004 s
OK
4.
0.004 s
OK
5.
0.008 s
OK
expand all
Performance tests
1.
0.084 s
OK
2.
0.076 s
OK
3.
0.088 s
OK
4.
0.080 s
OK
5.
0.076 s
OK
6.
0.076 s
OK
1.
0.080 s
OK
2.
0.072 s
OK
3.
0.072 s
OK
1.
0.076 s
OK
2.
0.076 s
OK
3.
0.080 s
OK
4.
0.076 s
OK
5.
0.080 s
OK