Tasks Details
hard
1.
ABSwaps
Calculate the minimum required number of swaps of neighbouring letters in a string built from the letters 'a' and 'b', after which the string would contain both "aaa" and "bbb" as substrings.
Task Score
75%
Correctness
100%
Performance
60%
You are given a string S consisting of letters 'a' and 'b'. The task is to rearrange letters in S so that it contains three consecutive letters 'a' and three consecutive letters 'b'. What is the minimum necessary number of swaps of neighbouring letters to achieve this?
Write a function:
class Solution { public int solution(String S); }
that, given a string S of length N, returns the number of swaps after which S would contain "aaa" and "bbb" as substrings. If it's not possible to rearrange the letters in such a way, the function should return −1.
Examples:
1. Given S = "ababab", the function should return 3. The sequence of swaps could be as follows: ababab → abaabb → aababb → aaabbb.
2. Given S = "abbbbaa", the function should return 4. The sequence of four swaps is: abbbbaa → babbbaa → bbabbaa → bbbabaa → bbbbaaa.
3. Given S = "bbbababaaab", the function should return 0. S already contains both "aaa" and "bbb" as substrings.
4. Given S = "abbabb", the function should return −1. It is not possible to obtain the required result from S as there are only two letters 'a'.
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 1 minutes
Notes
not defined yet
Code: 15:31:41 UTC,
java,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108
class Solution {
public int solution(String S) {
char[] s = S.toCharArray();
int[] N = new int[s.length];
int segmentCount = 0;
char currentChar = s[0];
N[segmentCount] = 1;
for (int i = 1; i < s.length; i++) {
char c = s[i];
if (c == currentChar)
N[segmentCount]++;
else {
currentChar = c;
N[++segmentCount] = 1;
}
}
segmentCount++;
int[] max = new int[] { 0, 0 };
int[] min = new int[] { BIG_NUMBER, BIG_NUMBER };
int[] count = new int[] { 0, 0 };
for (int i = 0; i < segmentCount; i++) {
int n = N[i];
int i2 = i % 2 == 0 ? 0 : 1;
count[i2] += n;
max[i2] = Math.max(max[i2], n);
min[i2] = Math.min(min[i2], n);
}
if (count[0] < 3 || count[1] < 3)
return -1;
if (max[0] >= 3 && max[1] >= 3)
return 0;
if (max[0] == 1 && max[1] == 1)
return 3;
if (max[0] >= 3) {
return findMin(N, segmentCount, 1);
} else if (max[1] >= 3) {
return findMin(N, segmentCount, 0);
} else {
int m = BIG_NUMBER;
for (int i = 0; i < segmentCount; i += 2) {
int n = N[i];
if (n == 2) {
if (i > 0) {
m = testSwap(N, segmentCount, m, 1, 1, i, N[i - 1], i - 2);
m = testSwap(N, segmentCount, m, 1, -2, i, N[i - 1]+N[i - 1], i - 2);
}
if (i < segmentCount - 2) {
m = testSwap(N, segmentCount, m, 1, 1, i, N[i + 1], i + 2);
m = testSwap(N, segmentCount, m, 1, -2, i, N[i + 1]+N[i + 1], i + 2);
}
}
}
for (int i = 1; i < segmentCount; i += 2) {
int n = N[i];
if (n == 2) {
if (i > 1) {
m = testSwap(N, segmentCount, m, 0, 1, i, N[i - 1], i - 2);
m = testSwap(N, segmentCount, m, 0, -2, i, N[i - 1]+N[i - 1], i - 2);
}
if (i < segmentCount - 2) {
m = testSwap(N, segmentCount, m, 0, 1, i, N[i + 1], i + 2);
m = testSwap(N, segmentCount, m, 0, -2, i, N[i + 1]+N[i + 1], i + 2);
}
}
}
return m;
}
}
int testSwap(int[] N, int segmentCount, int m, int start, int testValue, int base, int m1, int test_index) {
N[test_index] -= testValue;
N[base] += testValue;
m = Math.min(m, m1 + findMin(N, segmentCount, start));
N[test_index] += testValue;
N[base] -= testValue;
return m;
}
final static int BIG_NUMBER = 1000001;
private int findMin(int[] N, int size, int start) {
int m = BIG_NUMBER;
for (int i = start; i < size; i += 2) {
int i1 = N[i];
int l = (i > start) ? N[i - 1] : BIG_NUMBER;
int r = (i < size - 1 - start) ? N[i + 1] : BIG_NUMBER;
if (i1 == 1 && i > start && i<size-2) {
m = Math.min(m, l + r);
} else if (i1 == 2) {
if (i > start)
m = Math.min(m, l);
if (i < size - 2)
m = Math.min(m, r);
}
}
return m;
}}
Analysis
Code: 15:31:47 UTC,
java,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108
class Solution {
public int solution(String S) {
char[] s = S.toCharArray();
int[] N = new int[s.length];
int segmentCount = 0;
char currentChar = s[0];
N[segmentCount] = 1;
for (int i = 1; i < s.length; i++) {
char c = s[i];
if (c == currentChar)
N[segmentCount]++;
else {
currentChar = c;
N[++segmentCount] = 1;
}
}
segmentCount++;
int[] max = new int[] { 0, 0 };
int[] min = new int[] { BIG_NUMBER, BIG_NUMBER };
int[] count = new int[] { 0, 0 };
for (int i = 0; i < segmentCount; i++) {
int n = N[i];
int i2 = i % 2 == 0 ? 0 : 1;
count[i2] += n;
max[i2] = Math.max(max[i2], n);
min[i2] = Math.min(min[i2], n);
}
if (count[0] < 3 || count[1] < 3)
return -1;
if (max[0] >= 3 && max[1] >= 3)
return 0;
if (max[0] == 1 && max[1] == 1)
return 3;
if (max[0] >= 3) {
return findMin(N, segmentCount, 1);
} else if (max[1] >= 3) {
return findMin(N, segmentCount, 0);
} else {
int m = BIG_NUMBER;
for (int i = 0; i < segmentCount; i += 2) {
int n = N[i];
if (n == 2) {
if (i > 0) {
m = testSwap(N, segmentCount, m, 1, 1, i, N[i - 1], i - 2);
m = testSwap(N, segmentCount, m, 1, -2, i, N[i - 1]+N[i - 1], i - 2);
}
if (i < segmentCount - 2) {
m = testSwap(N, segmentCount, m, 1, 1, i, N[i + 1], i + 2);
m = testSwap(N, segmentCount, m, 1, -2, i, N[i + 1]+N[i + 1], i + 2);
}
}
}
for (int i = 1; i < segmentCount; i += 2) {
int n = N[i];
if (n == 2) {
if (i > 1) {
m = testSwap(N, segmentCount, m, 0, 1, i, N[i - 1], i - 2);
m = testSwap(N, segmentCount, m, 0, -2, i, N[i - 1]+N[i - 1], i - 2);
}
if (i < segmentCount - 2) {
m = testSwap(N, segmentCount, m, 0, 1, i, N[i + 1], i + 2);
m = testSwap(N, segmentCount, m, 0, -2, i, N[i + 1]+N[i + 1], i + 2);
}
}
}
return m;
}
}
int testSwap(int[] N, int segmentCount, int m, int start, int testValue, int base, int m1, int test_index) {
N[test_index] -= testValue;
N[base] += testValue;
m = Math.min(m, m1 + findMin(N, segmentCount, start));
N[test_index] += testValue;
N[base] -= testValue;
return m;
}
final static int BIG_NUMBER = 1000001;
private int findMin(int[] N, int size, int start) {
int m = BIG_NUMBER;
for (int i = start; i < size; i += 2) {
int i1 = N[i];
int l = (i > start) ? N[i - 1] : BIG_NUMBER;
int r = (i < size - 1 - start) ? N[i + 1] : BIG_NUMBER;
if (i1 == 1 && i > start && i<size-2) {
m = Math.min(m, l + r);
} else if (i1 == 2) {
if (i > start)
m = Math.min(m, l);
if (i < size - 2)
m = Math.min(m, r);
}
}
return m;
}}
Analysis
Code: 15:31:53 UTC,
java,
final,
score:
75
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108
class Solution {
public int solution(String S) {
char[] s = S.toCharArray();
int[] N = new int[s.length];
int segmentCount = 0;
char currentChar = s[0];
N[segmentCount] = 1;
for (int i = 1; i < s.length; i++) {
char c = s[i];
if (c == currentChar)
N[segmentCount]++;
else {
currentChar = c;
N[++segmentCount] = 1;
}
}
segmentCount++;
int[] max = new int[] { 0, 0 };
int[] min = new int[] { BIG_NUMBER, BIG_NUMBER };
int[] count = new int[] { 0, 0 };
for (int i = 0; i < segmentCount; i++) {
int n = N[i];
int i2 = i % 2 == 0 ? 0 : 1;
count[i2] += n;
max[i2] = Math.max(max[i2], n);
min[i2] = Math.min(min[i2], n);
}
if (count[0] < 3 || count[1] < 3)
return -1;
if (max[0] >= 3 && max[1] >= 3)
return 0;
if (max[0] == 1 && max[1] == 1)
return 3;
if (max[0] >= 3) {
return findMin(N, segmentCount, 1);
} else if (max[1] >= 3) {
return findMin(N, segmentCount, 0);
} else {
int m = BIG_NUMBER;
for (int i = 0; i < segmentCount; i += 2) {
int n = N[i];
if (n == 2) {
if (i > 0) {
m = testSwap(N, segmentCount, m, 1, 1, i, N[i - 1], i - 2);
m = testSwap(N, segmentCount, m, 1, -2, i, N[i - 1]+N[i - 1], i - 2);
}
if (i < segmentCount - 2) {
m = testSwap(N, segmentCount, m, 1, 1, i, N[i + 1], i + 2);
m = testSwap(N, segmentCount, m, 1, -2, i, N[i + 1]+N[i + 1], i + 2);
}
}
}
for (int i = 1; i < segmentCount; i += 2) {
int n = N[i];
if (n == 2) {
if (i > 1) {
m = testSwap(N, segmentCount, m, 0, 1, i, N[i - 1], i - 2);
m = testSwap(N, segmentCount, m, 0, -2, i, N[i - 1]+N[i - 1], i - 2);
}
if (i < segmentCount - 2) {
m = testSwap(N, segmentCount, m, 0, 1, i, N[i + 1], i + 2);
m = testSwap(N, segmentCount, m, 0, -2, i, N[i + 1]+N[i + 1], i + 2);
}
}
}
return m;
}
}
int testSwap(int[] N, int segmentCount, int m, int start, int testValue, int base, int m1, int test_index) {
N[test_index] -= testValue;
N[base] += testValue;
m = Math.min(m, m1 + findMin(N, segmentCount, start));
N[test_index] += testValue;
N[base] -= testValue;
return m;
}
final static int BIG_NUMBER = 1000001;
private int findMin(int[] N, int size, int start) {
int m = BIG_NUMBER;
for (int i = start; i < size; i += 2) {
int i1 = N[i];
int l = (i > start) ? N[i - 1] : BIG_NUMBER;
int r = (i < size - 1 - start) ? N[i + 1] : BIG_NUMBER;
if (i1 == 1 && i > start && i<size-2) {
m = Math.min(m, l + r);
} else if (i1 == 2) {
if (i > start)
m = Math.min(m, l);
if (i < size - 2)
m = Math.min(m, r);
}
}
return m;
}}
Analysis summary
The following issues have been detected: timeout errors.
Analysis
Detected time complexity:
O(N) or O(N**4)
expand all
Correctness tests
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.004 s
OK
4.
0.004 s
OK
5.
0.008 s
OK
6.
0.004 s
OK
7.
0.008 s
OK
8.
0.008 s
OK
9.
0.008 s
OK
10.
0.012 s
OK
11.
0.004 s
OK
12.
0.008 s
OK
13.
0.004 s
OK
14.
0.008 s
OK
15.
0.004 s
OK
16.
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
6.
0.008 s
OK
7.
0.008 s
OK
8.
0.012 s
OK
9.
0.008 s
OK
10.
0.008 s
OK
11.
0.012 s
OK
12.
0.012 s
OK
13.
0.008 s
OK
14.
0.012 s
OK
15.
0.012 s
OK
16.
0.008 s
OK
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.004 s
OK
4.
0.008 s
OK
5.
0.008 s
OK
6.
0.004 s
OK
7.
0.012 s
OK
8.
0.008 s
OK
9.
0.004 s
OK
10.
0.004 s
OK
11.
0.008 s
OK
12.
0.008 s
OK
13.
0.008 s
OK
14.
0.008 s
OK
15.
0.008 s
OK
16.
0.008 s
OK
17.
0.008 s
OK
18.
0.008 s
OK
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.004 s
OK
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.008 s
OK
4.
0.004 s
OK
1.
0.004 s
OK
2.
0.008 s
OK
3.
0.004 s
OK
4.
0.008 s
OK
expand all
Performance tests
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.004 s
OK
4.
0.008 s
OK
1.
0.004 s
OK
2.
0.008 s
OK
3.
0.004 s
OK
4.
0.004 s
OK
5.
0.004 s
OK
6.
0.008 s
OK
7.
0.004 s
OK
8.
0.004 s
OK
9.
0.004 s
OK
10.
0.004 s
OK
11.
0.004 s
OK
12.
0.008 s
OK
1.
0.056 s
OK
2.
0.052 s
OK
3.
0.052 s
OK
4.
0.060 s
OK
large_no_three_consecutive
No three consecutive letters in S are equal. Score x 2.
No three consecutive letters in S are equal. Score x 2.
✘
TIMEOUT ERROR
Killed. Hard limit reached: 6.000 sec.
Killed. Hard limit reached: 6.000 sec.
1.
6.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 6.000 sec.
2.
6.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 6.000 sec.
3.
6.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 6.000 sec.
4.
0.012 s
OK
5.
6.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 6.000 sec.
6.
0.016 s
OK
large_perf
Big performance package. Score x 2.
Big performance package. Score x 2.
✘
TIMEOUT ERROR
Killed. Hard limit reached: 6.000 sec.
Killed. Hard limit reached: 6.000 sec.
1.
6.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 6.000 sec.
2.
6.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 6.000 sec.
3.
0.068 s
OK
4.
6.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 6.000 sec.
5.
0.084 s
OK
6.
0.084 s
OK
7.
0.004 s
OK
8.
0.080 s
OK
9.
0.076 s
OK
10.
0.080 s
OK
11.
0.076 s
OK