Tasks Details
medium
Find the alphabetically largest string that can be obtained by performing some substitutions.
Task Score
54%
Correctness
100%
Performance
0%
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: 11:41:37 UTC,
java,
autosave
class Solution {
public String solution(String S) {
StringBuilder r = new StringBuilder();
char[] A = S.toCharArray();
BigInteger[] F = new BigInteger[A.length];
BigInteger sum = BigInteger.ZERO;
int j = A.length - 1;
for (int i = 0; i < A.length; i++) {
if (i == 0)
F[j] = BigInteger.ONE;
else if (i == 1)
F[j] = BigInteger.TWO;
else
F[j] = F[j + 1].add(F[j + 2]);
if (A[j] == 'b')
sum = sum.add(F[j]);
j--;
}
for (int i = 0; i < A.length; i++) {
if (sum.compareTo(F[i]) >= 0) {
sum = sum.subtract(F[i]);
r.append('b');
} else
r.append('a');
}
return r.toString();
}
}
Code: 11:41:44 UTC,
java,
verify,
result: Failed
import java.math.BigInteger;
class Solution {
public String solution(String S) {
StringBuilder r = new StringBuilder();
char[] A = S.toCharArray();
BigInteger[] F = new BigInteger[A.length];
BigInteger sum = BigInteger.ZERO;
int j = A.length - 1;
for (int i = 0; i < A.length; i++) {
if (i == 0)
F[j] = BigInteger.ONE;
else if (i == 1)
F[j] = BigInteger.TWO;
else
F[j] = F[j + 1].add(F[j + 2]);
if (A[j] == 'b')
sum = sum.add(F[j]);
j--;
}
for (int i = 0; i < A.length; i++) {
if (sum.compareTo(F[i]) >= 0) {
sum = sum.subtract(F[i]);
r.append('b');
} else
r.append('a');
}
return r.toString();
}
}
Analysis
Compile error
Solution.java:16: error: TWO has private access in BigInteger F[j] = BigInteger.TWO; ^ 1 error
Code: 11:42:09 UTC,
java,
autosave
import java.math.BigInteger;
class Solution {
public String solution(String S) {
StringBuilder r = new StringBuilder();
char[] A = S.toCharArray();
BigInteger[] F = new BigInteger[A.length];
BigInteger sum = BigInteger.ZERO;
int j = A.length - 1;
for (int i = 0; i < A.length; i++) {
if (i == 0)
F[j] = BigInteger.ONE;
else if (i == 1)
F[j] = BigInteger.ONE;
else
F[j] = F[j + 1].add(F[j + 2]);
if (A[j] == 'b')
sum = sum.add(F[j]);
j--;
}
for (int i = 0; i < A.length; i++) {
if (sum.compareTo(F[i]) >= 0) {
sum = sum.subtract(F[i]);
r.append('b');
} else
r.append('a');
}
return r.toString();
}
}
Code: 11:42:21 UTC,
java,
autosave
import java.math.BigInteger;
class Solution {
public String solution(String S) {
StringBuilder r = new StringBuilder();
char[] A = S.toCharArray();
BigInteger[] F = new BigInteger[A.length];
BigInteger sum = BigInteger.ZERO;
int j = A.length - 1;
for (int i = 0; i < A.length; i++) {
if (i == 0)
F[j] = BigInteger.ONE;
else if (i == 1)
F[j] = new BigInteger(2);
else
F[j] = F[j + 1].add(F[j + 2]);
if (A[j] == 'b')
sum = sum.add(F[j]);
j--;
}
for (int i = 0; i < A.length; i++) {
if (sum.compareTo(F[i]) >= 0) {
sum = sum.subtract(F[i]);
r.append('b');
} else
r.append('a');
}
return r.toString();
}
}
Code: 11:42:22 UTC,
java,
verify,
result: Failed
import java.math.BigInteger;
class Solution {
public String solution(String S) {
StringBuilder r = new StringBuilder();
char[] A = S.toCharArray();
BigInteger[] F = new BigInteger[A.length];
BigInteger sum = BigInteger.ZERO;
int j = A.length - 1;
for (int i = 0; i < A.length; i++) {
if (i == 0)
F[j] = BigInteger.ONE;
else if (i == 1)
F[j] = new BigInteger(2);
else
F[j] = F[j + 1].add(F[j + 2]);
if (A[j] == 'b')
sum = sum.add(F[j]);
j--;
}
for (int i = 0; i < A.length; i++) {
if (sum.compareTo(F[i]) >= 0) {
sum = sum.subtract(F[i]);
r.append('b');
} else
r.append('a');
}
return r.toString();
}
}
Analysis
Compile error
Solution.java:16: error: BigInteger(long) has private access in BigInteger F[j] = new BigInteger(2); ^ 1 error
Code: 11:42:36 UTC,
java,
verify,
result: Passed
import java.math.BigInteger;
class Solution {
public String solution(String S) {
StringBuilder r = new StringBuilder();
char[] A = S.toCharArray();
BigInteger[] F = new BigInteger[A.length];
BigInteger sum = BigInteger.ZERO;
int j = A.length - 1;
for (int i = 0; i < A.length; i++) {
if (i == 0)
F[j] = BigInteger.ONE;
else if (i == 1)
F[j] = new BigInteger("2");
else
F[j] = F[j + 1].add(F[j + 2]);
if (A[j] == 'b')
sum = sum.add(F[j]);
j--;
}
for (int i = 0; i < A.length; i++) {
if (sum.compareTo(F[i]) >= 0) {
sum = sum.subtract(F[i]);
r.append('b');
} else
r.append('a');
}
return r.toString();
}
}
Analysis
Code: 11:42:44 UTC,
java,
verify,
result: Passed
import java.math.BigInteger;
class Solution {
public String solution(String S) {
StringBuilder r = new StringBuilder();
char[] A = S.toCharArray();
BigInteger[] F = new BigInteger[A.length];
BigInteger sum = BigInteger.ZERO;
int j = A.length - 1;
for (int i = 0; i < A.length; i++) {
if (i == 0)
F[j] = BigInteger.ONE;
else if (i == 1)
F[j] = new BigInteger("2");
else
F[j] = F[j + 1].add(F[j + 2]);
if (A[j] == 'b')
sum = sum.add(F[j]);
j--;
}
for (int i = 0; i < A.length; i++) {
if (sum.compareTo(F[i]) >= 0) {
sum = sum.subtract(F[i]);
r.append('b');
} else
r.append('a');
}
return r.toString();
}
}
Analysis
Code: 11:42:49 UTC,
java,
final,
score:
54
import java.math.BigInteger;
class Solution {
public String solution(String S) {
StringBuilder r = new StringBuilder();
char[] A = S.toCharArray();
BigInteger[] F = new BigInteger[A.length];
BigInteger sum = BigInteger.ZERO;
int j = A.length - 1;
for (int i = 0; i < A.length; i++) {
if (i == 0)
F[j] = BigInteger.ONE;
else if (i == 1)
F[j] = new BigInteger("2");
else
F[j] = F[j + 1].add(F[j + 2]);
if (A[j] == 'b')
sum = sum.add(F[j]);
j--;
}
for (int i = 0; i < A.length; i++) {
if (sum.compareTo(F[i]) >= 0) {
sum = sum.subtract(F[i]);
r.append('b');
} else
r.append('a');
}
return r.toString();
}
}
Analysis summary
The following issues have been detected: timeout errors.
Analysis
Detected time complexity:
O(N**2)
expand all
Correctness tests
1.
0.012 s
OK
2.
0.008 s
OK
3.
0.008 s
OK
4.
0.004 s
OK
5.
0.008 s
OK
1.
0.004 s
OK
2.
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.008 s
OK
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.008 s
OK
4.
0.004 s
OK
5.
0.004 s
OK
1.
0.004 s
OK
2.
0.008 s
OK
3.
0.004 s
OK
4.
0.008 s
OK
5.
0.008 s
OK
6.
0.008 s
OK
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.012 s
OK
4.
0.004 s
OK
5.
0.004 s
OK
expand all
Performance tests
big_simple
Simple big test. N = 100,000. Score x 3.
Simple big test. N = 100,000. Score x 3.
✘
TIMEOUT ERROR
running time: 2.544 sec., time limit: 0.272 sec.
running time: 2.544 sec., time limit: 0.272 sec.
1.
2.544 s
TIMEOUT ERROR,
running time: 2.544 sec., time limit: 0.272 sec.
stderr:
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space at java.math.BigInteger.add(BigInteger.java:1324) at java.math.BigInteger.add(BigInteger.java:1230) at Solution.solution(Solution.java:18) at Exec.run(exec.java:48) at Exec.main(exec.java:34)
2.
2.520 s
TIMEOUT ERROR,
running time: 2.520 sec., time limit: 0.304 sec.
stderr:
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space at java.math.BigInteger.add(BigInteger.java:1324) at java.math.BigInteger.add(BigInteger.java:1230) at Solution.solution(Solution.java:18) at Exec.run(exec.java:48) at Exec.main(exec.java:34)
3.
3.288 s
TIMEOUT ERROR,
running time: 3.288 sec., time limit: 0.304 sec.
stderr:
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space at java.math.BigInteger.add(BigInteger.java:1324) at java.math.BigInteger.add(BigInteger.java:1230) at Solution.solution(Solution.java:21) at Exec.run(exec.java:48) at Exec.main(exec.java:34)
4.
3.304 s
TIMEOUT ERROR,
running time: 3.304 sec., time limit: 0.288 sec.
stderr:
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space at java.math.BigInteger.add(BigInteger.java:1324) at java.math.BigInteger.add(BigInteger.java:1230) at Solution.solution(Solution.java:21) at Exec.run(exec.java:48) at Exec.main(exec.java:34)
5.
2.544 s
TIMEOUT ERROR,
running time: 2.544 sec., time limit: 0.304 sec.
stderr:
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space at java.math.BigInteger.add(BigInteger.java:1324) at java.math.BigInteger.add(BigInteger.java:1230) at Solution.solution(Solution.java:21) at Exec.run(exec.java:48) at Exec.main(exec.java:34)
6.
2.664 s
TIMEOUT ERROR,
running time: 2.664 sec., time limit: 0.304 sec.
stderr:
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space at java.math.BigInteger.add(BigInteger.java:1324) at java.math.BigInteger.add(BigInteger.java:1230) at Solution.solution(Solution.java:18) at Exec.run(exec.java:48) at Exec.main(exec.java:34)
big_monotone
Monotone string. N = 100,000.
Monotone string. N = 100,000.
✘
TIMEOUT ERROR
running time: 3.336 sec., time limit: 0.304 sec.
running time: 3.336 sec., time limit: 0.304 sec.
1.
3.336 s
TIMEOUT ERROR,
running time: 3.336 sec., time limit: 0.304 sec.
stderr:
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space at java.math.BigInteger.add(BigInteger.java:1324) at java.math.BigInteger.add(BigInteger.java:1230) at Solution.solution(Solution.java:21) at Exec.run(exec.java:48) at Exec.main(exec.java:34)
2.
2.116 s
TIMEOUT ERROR,
running time: 2.116 sec., time limit: 0.272 sec.
stderr:
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space at java.math.BigInteger.add(BigInteger.java:1324) at java.math.BigInteger.add(BigInteger.java:1230) at Solution.solution(Solution.java:21) at Exec.run(exec.java:48) at Exec.main(exec.java:34)
3.
1.820 s
TIMEOUT ERROR,
running time: 1.820 sec., time limit: 0.272 sec.
stderr:
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space at java.math.BigInteger.add(BigInteger.java:1324) at java.math.BigInteger.add(BigInteger.java:1230) at Solution.solution(Solution.java:18) at Exec.run(exec.java:48) at Exec.main(exec.java:34)
random_big
Random big string. N = 100,000.
Random big string. N = 100,000.
✘
TIMEOUT ERROR
running time: 2.516 sec., time limit: 0.288 sec.
running time: 2.516 sec., time limit: 0.288 sec.
1.
2.516 s
TIMEOUT ERROR,
running time: 2.516 sec., time limit: 0.288 sec.
stderr:
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space at java.math.BigInteger.add(BigInteger.java:1324) at java.math.BigInteger.add(BigInteger.java:1230) at Solution.solution(Solution.java:18) at Exec.run(exec.java:48) at Exec.main(exec.java:34)
2.
2.480 s
TIMEOUT ERROR,
running time: 2.480 sec., time limit: 0.272 sec.
stderr:
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space at java.math.BigInteger.add(BigInteger.java:1324) at java.math.BigInteger.add(BigInteger.java:1230) at Solution.solution(Solution.java:21) at Exec.run(exec.java:48) at Exec.main(exec.java:34)
3.
2.496 s
TIMEOUT ERROR,
running time: 2.496 sec., time limit: 0.288 sec.
stderr:
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space at java.math.BigInteger.add(BigInteger.java:1324) at java.math.BigInteger.add(BigInteger.java:1230) at Solution.solution(Solution.java:21) at Exec.run(exec.java:48) at Exec.main(exec.java:34)
4.
2.568 s
TIMEOUT ERROR,
running time: 2.568 sec., time limit: 0.288 sec.
stderr:
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space at java.math.BigInteger.add(BigInteger.java:1324) at java.math.BigInteger.add(BigInteger.java:1230) at Solution.solution(Solution.java:21) at Exec.run(exec.java:48) at Exec.main(exec.java:34)
5.
2.504 s
TIMEOUT ERROR,
running time: 2.504 sec., time limit: 0.288 sec.
stderr:
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space at java.math.BigInteger.add(BigInteger.java:1324) at java.math.BigInteger.add(BigInteger.java:1230) at Solution.solution(Solution.java:21) at Exec.run(exec.java:48) at Exec.main(exec.java:34)