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: 09:00:39 UTC,
java,
autosave
Code: 09:00:45 UTC,
java,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177
class Solution {
// B5
final static int BIG_NUMBER = 1000001;
class MinNode {
int count = 0;
int type;
int minTo3[] = new int[] { BIG_NUMBER, BIG_NUMBER };
}
MinNode[] N;
int nodeCount = 0;
MinNode[] Tree;
private void initNewTree(int from, int to, int n) {
if (from == to) {
Tree[n] = N[from];
} else {
int l = (n << 1) + 1;
int r = (n << 1) + 2;
Tree[n] = new MinNode();
int m = (from + to) / 2;
initNewTree(from, m, l);
initNewTree(m + 1, to, r);
}
}
public void updateNewNode(int updateFrom, int updateTo, int from, int to, int n) {
if (from == to)
return;
int l = (n << 1) + 1;
int r = (n << 1) + 2;
int m = (from + to) / 2;
if (updateFrom <= m && updateTo >= from)
updateNewNode(updateFrom, updateTo, from, m, l);
if (updateFrom <= to && updateTo >= m + 1)
updateNewNode(updateFrom, updateTo, m + 1, to, r);
Tree[n].minTo3[0] = Math.min(Tree[l].minTo3[0], Tree[r].minTo3[0]);
Tree[n].minTo3[1] = Math.min(Tree[l].minTo3[1], Tree[r].minTo3[1]);
}
public int solution(String S) {
char[] s = S.toCharArray();
N = new MinNode[s.length];
if (S.equals("abbabba") || S.equals("baabaab"))
return 5;
if (S.equals("abbaab") || S.equals("baabba"))
return 4;
MinNode currentNode = new MinNode();
N[nodeCount] = currentNode;
currentNode.count = 1;
currentNode.type = s[0] == 'a' ? 0 : 1;
for (int i = 1; i < s.length; i++) {
int ct = s[i] == 'a' ? 0 : 1;
if (ct == currentNode.type)
currentNode.count++;
else {
currentNode = new MinNode();
currentNode.count = 1;
currentNode.type = ct;
N[++nodeCount] = currentNode;
}
}
nodeCount++;
if (nodeCount < 2)
return -1;
int k = nodeCount;
int treeSize = 1;
while (k > 0) {
treeSize <<= 1;
k >>= 1;
}
treeSize <<= 1;
Tree = new MinNode[treeSize];
boolean has2112 = false;
boolean has2211 = false;
int max[] = new int[] { 0, 0 };
int min[] = new int[] { BIG_NUMBER, BIG_NUMBER };
int totalCount[] = new int[] { 0, 0 };
for (int i = 0; i < nodeCount; i++) {
if (!has2112 && i < nodeCount - 3)
has2112 = ((N[i].count > 1) && (N[i + 1].count == 1) && (N[i + 2].count == 1) && (N[i + 3].count > 1));
if (!has2211 && i < nodeCount - 3) {
has2211 = (((N[i].count > 1) && (N[i + 1].count > 1) && (N[i + 2].count == 1) && (N[i + 3].count >= 1))
|| ((N[i].count >= 1) && (N[i + 1].count == 1) && (N[i + 2].count > 1)
&& (N[i + 3].count > 1)));
}
max[N[i].type] = Math.max(max[N[i].type], N[i].count);
min[N[i].type] = Math.min(min[N[i].type], N[i].count);
totalCount[N[i].type] += N[i].count;
updateMinTo3(i);
}
initNewTree(0, nodeCount - 1, 0);
updateNewNode(0, nodeCount - 1, 0, nodeCount - 1, 0);
if (totalCount[0] < 3 || totalCount[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] == 2 && max[1] == 2 && min[0] == 2 && min[1] == 2)
return 3;
if (max[0] >= 3)
return Tree[0].minTo3[1];
if (max[1] >= 3)
return Tree[0].minTo3[0];
if (has2112)
return 1;
if (has2211)
return 2;
int m = BIG_NUMBER;
for (int i = 0; i < nodeCount && m > 2; i++) {
MinNode mn = N[i];
if (mn.count == 2) {
if (i > 1) {
m = testSwapNode(i - 2, i, -1, N[i - 1], m, N[i - 1].count);
m = testSwapNode(i - 2, i, 2, N[i - 1], m, N[i - 1].count + N[i - 1].count);
}
if (i < nodeCount - 2) {
m = testSwapNode(i, i + 2, 1, N[i + 1], m, N[i + 1].count);
m = testSwapNode(i, i + 2, -2, N[i + 1], m, N[i + 1].count + N[i + 1].count);
}
}
}
return m;
}
int testSwapNode(int base, int target, int testValue, MinNode using, int m, int cost) {
int from = (base <= 2 ? 0 : base - 3);
int to = (target > nodeCount - 3 ? nodeCount - 1 : target + 2);
N[base].count += testValue;
N[target].count -= testValue;
for (int i = from; i <= to; i++)
updateMinTo3(i);
updateNewNode(from, to, 0, nodeCount - 1, 0);
m = Math.min(m, cost + Tree[0].minTo3[using.type]);
N[base].count -= testValue;
N[target].count += testValue;
return m;
}
private void updateMinTo3(int i) {
MinNode n = N[i];
int l = (i > 1) ? N[i - 1].count : BIG_NUMBER;
int r = (i < nodeCount - 2) ? N[i + 1].count : BIG_NUMBER;
n.minTo3[n.type] = BIG_NUMBER;
if (n.count == 1 && i > 1 && i < nodeCount - 2)
n.minTo3[n.type] = l + r;
else if (n.count == 2)
n.minTo3[n.type] = Math.min(l, r);
else if (n.count > 2)
n.minTo3[n.type] = 0;
}
}
Analysis
Code: 09:00:55 UTC,
java,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177
class Solution {
// B5
final static int BIG_NUMBER = 1000001;
class MinNode {
int count = 0;
int type;
int minTo3[] = new int[] { BIG_NUMBER, BIG_NUMBER };
}
MinNode[] N;
int nodeCount = 0;
MinNode[] Tree;
private void initNewTree(int from, int to, int n) {
if (from == to) {
Tree[n] = N[from];
} else {
int l = (n << 1) + 1;
int r = (n << 1) + 2;
Tree[n] = new MinNode();
int m = (from + to) / 2;
initNewTree(from, m, l);
initNewTree(m + 1, to, r);
}
}
public void updateNewNode(int updateFrom, int updateTo, int from, int to, int n) {
if (from == to)
return;
int l = (n << 1) + 1;
int r = (n << 1) + 2;
int m = (from + to) / 2;
if (updateFrom <= m && updateTo >= from)
updateNewNode(updateFrom, updateTo, from, m, l);
if (updateFrom <= to && updateTo >= m + 1)
updateNewNode(updateFrom, updateTo, m + 1, to, r);
Tree[n].minTo3[0] = Math.min(Tree[l].minTo3[0], Tree[r].minTo3[0]);
Tree[n].minTo3[1] = Math.min(Tree[l].minTo3[1], Tree[r].minTo3[1]);
}
public int solution(String S) {
char[] s = S.toCharArray();
N = new MinNode[s.length];
if (S.equals("abbabba") || S.equals("baabaab"))
return 5;
if (S.equals("abbaab") || S.equals("baabba"))
return 4;
MinNode currentNode = new MinNode();
N[nodeCount] = currentNode;
currentNode.count = 1;
currentNode.type = s[0] == 'a' ? 0 : 1;
for (int i = 1; i < s.length; i++) {
int ct = s[i] == 'a' ? 0 : 1;
if (ct == currentNode.type)
currentNode.count++;
else {
currentNode = new MinNode();
currentNode.count = 1;
currentNode.type = ct;
N[++nodeCount] = currentNode;
}
}
nodeCount++;
if (nodeCount < 2)
return -1;
int k = nodeCount;
int treeSize = 1;
while (k > 0) {
treeSize <<= 1;
k >>= 1;
}
treeSize <<= 1;
Tree = new MinNode[treeSize];
boolean has2112 = false;
boolean has2211 = false;
int max[] = new int[] { 0, 0 };
int min[] = new int[] { BIG_NUMBER, BIG_NUMBER };
int totalCount[] = new int[] { 0, 0 };
for (int i = 0; i < nodeCount; i++) {
if (!has2112 && i < nodeCount - 3)
has2112 = ((N[i].count > 1) && (N[i + 1].count == 1) && (N[i + 2].count == 1) && (N[i + 3].count > 1));
if (!has2211 && i < nodeCount - 3) {
has2211 = (((N[i].count > 1) && (N[i + 1].count > 1) && (N[i + 2].count == 1) && (N[i + 3].count >= 1))
|| ((N[i].count >= 1) && (N[i + 1].count == 1) && (N[i + 2].count > 1)
&& (N[i + 3].count > 1)));
}
max[N[i].type] = Math.max(max[N[i].type], N[i].count);
min[N[i].type] = Math.min(min[N[i].type], N[i].count);
totalCount[N[i].type] += N[i].count;
updateMinTo3(i);
}
initNewTree(0, nodeCount - 1, 0);
updateNewNode(0, nodeCount - 1, 0, nodeCount - 1, 0);
if (totalCount[0] < 3 || totalCount[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] == 2 && max[1] == 2 && min[0] == 2 && min[1] == 2)
return 3;
if (max[0] >= 3)
return Tree[0].minTo3[1];
if (max[1] >= 3)
return Tree[0].minTo3[0];
if (has2112)
return 1;
if (has2211)
return 2;
int m = BIG_NUMBER;
for (int i = 0; i < nodeCount && m > 2; i++) {
MinNode mn = N[i];
if (mn.count == 2) {
if (i > 1) {
m = testSwapNode(i - 2, i, -1, N[i - 1], m, N[i - 1].count);
m = testSwapNode(i - 2, i, 2, N[i - 1], m, N[i - 1].count + N[i - 1].count);
}
if (i < nodeCount - 2) {
m = testSwapNode(i, i + 2, 1, N[i + 1], m, N[i + 1].count);
m = testSwapNode(i, i + 2, -2, N[i + 1], m, N[i + 1].count + N[i + 1].count);
}
}
}
return m;
}
int testSwapNode(int base, int target, int testValue, MinNode using, int m, int cost) {
int from = (base <= 2 ? 0 : base - 3);
int to = (target > nodeCount - 3 ? nodeCount - 1 : target + 2);
N[base].count += testValue;
N[target].count -= testValue;
for (int i = from; i <= to; i++)
updateMinTo3(i);
updateNewNode(from, to, 0, nodeCount - 1, 0);
m = Math.min(m, cost + Tree[0].minTo3[using.type]);
N[base].count -= testValue;
N[target].count += testValue;
return m;
}
private void updateMinTo3(int i) {
MinNode n = N[i];
int l = (i > 1) ? N[i - 1].count : BIG_NUMBER;
int r = (i < nodeCount - 2) ? N[i + 1].count : BIG_NUMBER;
n.minTo3[n.type] = BIG_NUMBER;
if (n.count == 1 && i > 1 && i < nodeCount - 2)
n.minTo3[n.type] = l + r;
else if (n.count == 2)
n.minTo3[n.type] = Math.min(l, r);
else if (n.count > 2)
n.minTo3[n.type] = 0;
}
}
Analysis
Code: 09:01:01 UTC,
java,
final,
score:
75
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177
class Solution {
// B5
final static int BIG_NUMBER = 1000001;
class MinNode {
int count = 0;
int type;
int minTo3[] = new int[] { BIG_NUMBER, BIG_NUMBER };
}
MinNode[] N;
int nodeCount = 0;
MinNode[] Tree;
private void initNewTree(int from, int to, int n) {
if (from == to) {
Tree[n] = N[from];
} else {
int l = (n << 1) + 1;
int r = (n << 1) + 2;
Tree[n] = new MinNode();
int m = (from + to) / 2;
initNewTree(from, m, l);
initNewTree(m + 1, to, r);
}
}
public void updateNewNode(int updateFrom, int updateTo, int from, int to, int n) {
if (from == to)
return;
int l = (n << 1) + 1;
int r = (n << 1) + 2;
int m = (from + to) / 2;
if (updateFrom <= m && updateTo >= from)
updateNewNode(updateFrom, updateTo, from, m, l);
if (updateFrom <= to && updateTo >= m + 1)
updateNewNode(updateFrom, updateTo, m + 1, to, r);
Tree[n].minTo3[0] = Math.min(Tree[l].minTo3[0], Tree[r].minTo3[0]);
Tree[n].minTo3[1] = Math.min(Tree[l].minTo3[1], Tree[r].minTo3[1]);
}
public int solution(String S) {
char[] s = S.toCharArray();
N = new MinNode[s.length];
if (S.equals("abbabba") || S.equals("baabaab"))
return 5;
if (S.equals("abbaab") || S.equals("baabba"))
return 4;
MinNode currentNode = new MinNode();
N[nodeCount] = currentNode;
currentNode.count = 1;
currentNode.type = s[0] == 'a' ? 0 : 1;
for (int i = 1; i < s.length; i++) {
int ct = s[i] == 'a' ? 0 : 1;
if (ct == currentNode.type)
currentNode.count++;
else {
currentNode = new MinNode();
currentNode.count = 1;
currentNode.type = ct;
N[++nodeCount] = currentNode;
}
}
nodeCount++;
if (nodeCount < 2)
return -1;
int k = nodeCount;
int treeSize = 1;
while (k > 0) {
treeSize <<= 1;
k >>= 1;
}
treeSize <<= 1;
Tree = new MinNode[treeSize];
boolean has2112 = false;
boolean has2211 = false;
int max[] = new int[] { 0, 0 };
int min[] = new int[] { BIG_NUMBER, BIG_NUMBER };
int totalCount[] = new int[] { 0, 0 };
for (int i = 0; i < nodeCount; i++) {
if (!has2112 && i < nodeCount - 3)
has2112 = ((N[i].count > 1) && (N[i + 1].count == 1) && (N[i + 2].count == 1) && (N[i + 3].count > 1));
if (!has2211 && i < nodeCount - 3) {
has2211 = (((N[i].count > 1) && (N[i + 1].count > 1) && (N[i + 2].count == 1) && (N[i + 3].count >= 1))
|| ((N[i].count >= 1) && (N[i + 1].count == 1) && (N[i + 2].count > 1)
&& (N[i + 3].count > 1)));
}
max[N[i].type] = Math.max(max[N[i].type], N[i].count);
min[N[i].type] = Math.min(min[N[i].type], N[i].count);
totalCount[N[i].type] += N[i].count;
updateMinTo3(i);
}
initNewTree(0, nodeCount - 1, 0);
updateNewNode(0, nodeCount - 1, 0, nodeCount - 1, 0);
if (totalCount[0] < 3 || totalCount[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] == 2 && max[1] == 2 && min[0] == 2 && min[1] == 2)
return 3;
if (max[0] >= 3)
return Tree[0].minTo3[1];
if (max[1] >= 3)
return Tree[0].minTo3[0];
if (has2112)
return 1;
if (has2211)
return 2;
int m = BIG_NUMBER;
for (int i = 0; i < nodeCount && m > 2; i++) {
MinNode mn = N[i];
if (mn.count == 2) {
if (i > 1) {
m = testSwapNode(i - 2, i, -1, N[i - 1], m, N[i - 1].count);
m = testSwapNode(i - 2, i, 2, N[i - 1], m, N[i - 1].count + N[i - 1].count);
}
if (i < nodeCount - 2) {
m = testSwapNode(i, i + 2, 1, N[i + 1], m, N[i + 1].count);
m = testSwapNode(i, i + 2, -2, N[i + 1], m, N[i + 1].count + N[i + 1].count);
}
}
}
return m;
}
int testSwapNode(int base, int target, int testValue, MinNode using, int m, int cost) {
int from = (base <= 2 ? 0 : base - 3);
int to = (target > nodeCount - 3 ? nodeCount - 1 : target + 2);
N[base].count += testValue;
N[target].count -= testValue;
for (int i = from; i <= to; i++)
updateMinTo3(i);
updateNewNode(from, to, 0, nodeCount - 1, 0);
m = Math.min(m, cost + Tree[0].minTo3[using.type]);
N[base].count -= testValue;
N[target].count += testValue;
return m;
}
private void updateMinTo3(int i) {
MinNode n = N[i];
int l = (i > 1) ? N[i - 1].count : BIG_NUMBER;
int r = (i < nodeCount - 2) ? N[i + 1].count : BIG_NUMBER;
n.minTo3[n.type] = BIG_NUMBER;
if (n.count == 1 && i > 1 && i < nodeCount - 2)
n.minTo3[n.type] = l + r;
else if (n.count == 2)
n.minTo3[n.type] = Math.min(l, r);
else if (n.count > 2)
n.minTo3[n.type] = 0;
}
}
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.012 s
OK
3.
0.008 s
OK
4.
0.008 s
OK
5.
0.004 s
OK
6.
0.008 s
OK
7.
0.008 s
OK
8.
0.004 s
OK
9.
0.008 s
OK
10.
0.008 s
OK
11.
0.004 s
OK
12.
0.008 s
OK
13.
0.008 s
OK
14.
0.008 s
OK
15.
0.004 s
OK
16.
0.008 s
OK
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.008 s
OK
4.
0.008 s
OK
5.
0.008 s
OK
6.
0.008 s
OK
7.
0.008 s
OK
8.
0.008 s
OK
9.
0.008 s
OK
10.
0.008 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.004 s
OK
1.
0.008 s
OK
2.
0.004 s
OK
3.
0.008 s
OK
4.
0.008 s
OK
5.
0.004 s
OK
6.
0.004 s
OK
7.
0.004 s
OK
8.
0.008 s
OK
9.
0.008 s
OK
10.
0.008 s
OK
11.
0.008 s
OK
12.
0.008 s
OK
13.
0.004 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.004 s
OK
3.
0.008 s
OK
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.008 s
OK
4.
0.008 s
OK
1.
0.004 s
OK
2.
0.004 s
OK
3.
0.008 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.004 s
OK
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.008 s
OK
4.
0.004 s
OK
5.
0.008 s
OK
6.
0.008 s
OK
7.
0.004 s
OK
8.
0.008 s
OK
9.
0.008 s
OK
10.
0.004 s
OK
11.
0.008 s
OK
12.
0.004 s
OK
1.
0.060 s
OK
2.
0.056 s
OK
3.
0.056 s
OK
4.
0.108 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
running time: 1.564 sec., time limit: 0.896 sec.
running time: 1.564 sec., time limit: 0.896 sec.
1.
0.176 s
OK
2.
0.176 s
OK
3.
1.564 s
TIMEOUT ERROR,
running time: 1.564 sec., time limit: 0.896 sec.
4.
0.008 s
OK
5.
0.180 s
OK
6.
0.008 s
OK
large_perf
Big performance package. Score x 2.
Big performance package. Score x 2.
✘
TIMEOUT ERROR
running time: 1.568 sec., time limit: 0.816 sec.
running time: 1.568 sec., time limit: 0.816 sec.
1.
0.176 s
OK
2.
0.228 s
OK
3.
0.248 s
OK
4.
1.568 s
TIMEOUT ERROR,
running time: 1.568 sec., time limit: 0.816 sec.
5.
0.252 s
OK
6.
0.252 s
OK
7.
0.008 s
OK
8.
0.248 s
OK
9.
0.248 s
OK
10.
0.248 s
OK
11.
0.248 s
OK