Test results - Codility

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

100%

Correctness

100%

Performance

100%

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'.

Solution

Programming language used Java 11

Time spent on task 2 minutes

Notes

not defined yet

Code: 11:13:35 UTC, java, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(String S) {
        // write your code in Java SE 8
    }
}

Code: 11:13:49 UTC, java, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

class Solution {
    public int solution(String S) {
        // write your code in Java SE 8
    }
}

Code: 11:13:59 UTC, java11, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

class Solution {
    public int solution(String S) {
        // write your code in Java SE 11
    }
}

Code: 11:14:14 UTC, java11, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

class Solution {
	public int solution(String S) {

		int[] count = new int[] {0, 0};
		int[][] pos = new int[2][S.length()];
		int[] poscount = new int[] {0, 0};

		boolean[] has3 = new boolean[] {false, false};

		for (int i = 0; i < S.length(); i++) {
			int n = S.charAt(i) - 'a';
			count[n]++;
			if (i > 1 && !has3[n])
				has3[n] = (S.charAt(i) == S.charAt(i - 1) && S.charAt(i) == S.charAt(i - 2));
			pos[n][poscount[n]++] = i;
		}

		if (count[0] < 3 || count[1] < 3)
			return -1;

		for (int i = 0; i < 2; i++)
			if (has3[i]) {
				int ans = S.length();
				int i2 = i == 0 ? 1 : 0;
				for (int j = 0; j < poscount[i2] - 2; j++)
					ans = Math.min(ans, pos[i2][j + 2] - pos[i2][j] - 2);
				return ans;
			}

		Map<String, Integer> d = new HashMap<>();
		Queue<String> q = new LinkedList<>();
		for (int i = 0; i < S.length(); i++) {
			String w = i + 8 < S.length() ? S.substring(i, i + 8) : S.substring(i);
			if (!d.containsKey(w)) {
				d.put(w, 0);
				q.add(w);
			}
		}
		while (!q.isEmpty()) {
			String w = q.remove();
			if (w.indexOf("aaa") != -1 && w.indexOf("bbb") != -1)
				return d.get(w);
			for (int i = 0; i < w.length() - 1; i++) {
				String w2 = w.substring(0, i) + w.charAt(i + 1) + w.charAt(i) + w.substring(i + 2);
				if (!d.containsKey(w2)) {
					d.put(w2, d.get(w) + 1);
					q.add(w2);
				}
			}
		}
		return 0;
	}
}

Code: 11:14:15 UTC, java11, verify, result: Passed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

class Solution {
	public int solution(String S) {

		int[] count = new int[] {0, 0};
		int[][] pos = new int[2][S.length()];
		int[] poscount = new int[] {0, 0};

		boolean[] has3 = new boolean[] {false, false};

		for (int i = 0; i < S.length(); i++) {
			int n = S.charAt(i) - 'a';
			count[n]++;
			if (i > 1 && !has3[n])
				has3[n] = (S.charAt(i) == S.charAt(i - 1) && S.charAt(i) == S.charAt(i - 2));
			pos[n][poscount[n]++] = i;
		}

		if (count[0] < 3 || count[1] < 3)
			return -1;

		for (int i = 0; i < 2; i++)
			if (has3[i]) {
				int ans = S.length();
				int i2 = i == 0 ? 1 : 0;
				for (int j = 0; j < poscount[i2] - 2; j++)
					ans = Math.min(ans, pos[i2][j + 2] - pos[i2][j] - 2);
				return ans;
			}

		Map<String, Integer> d = new HashMap<>();
		Queue<String> q = new LinkedList<>();
		for (int i = 0; i < S.length(); i++) {
			String w = i + 8 < S.length() ? S.substring(i, i + 8) : S.substring(i);
			if (!d.containsKey(w)) {
				d.put(w, 0);
				q.add(w);
			}
		}
		while (!q.isEmpty()) {
			String w = q.remove();
			if (w.indexOf("aaa") != -1 && w.indexOf("bbb") != -1)
				return d.get(w);
			for (int i = 0; i < w.length() - 1; i++) {
				String w2 = w.substring(0, i) + w.charAt(i + 1) + w.charAt(i) + w.substring(i + 2);
				if (!d.containsKey(w2)) {
					d.put(w2, d.get(w) + 1);
					q.add(w2);
				}
			}
		}
		return 0;
	}
}

Analysis

expand all Example tests

▶

example1
First example test.

✔

0.072 s

▶

example2
Second example test.

✔

0.004 s

▶

example3
Third example test.

✔

0.004 s

▶

example4
Fourth example test.

✔

0.004 s

Code: 11:14:33 UTC, java11, verify, result: Passed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

class Solution {
	public int solution(String S) {

		int[] count = new int[] {0, 0};
		int[][] pos = new int[2][S.length()];
		int[] poscount = new int[] {0, 0};

		boolean[] has3 = new boolean[] {false, false};

		for (int i = 0; i < S.length(); i++) {
			int n = S.charAt(i) - 'a';
			count[n]++;
			if (i > 1 && !has3[n])
				has3[n] = (S.charAt(i) == S.charAt(i - 1) && S.charAt(i) == S.charAt(i - 2));
			pos[n][poscount[n]++] = i;
		}

		if (count[0] < 3 || count[1] < 3)
			return -1;

		for (int i = 0; i < 2; i++)
			if (has3[i]) {
				int ans = S.length();
				int i2 = i == 0 ? 1 : 0;
				for (int j = 0; j < poscount[i2] - 2; j++)
					ans = Math.min(ans, pos[i2][j + 2] - pos[i2][j] - 2);
				return ans;
			}

		Map<String, Integer> d = new HashMap<>();
		Queue<String> q = new LinkedList<>();
		for (int i = 0; i < S.length(); i++) {
			String w = i + 8 < S.length() ? S.substring(i, i + 8) : S.substring(i);
			if (!d.containsKey(w)) {
				d.put(w, 0);
				q.add(w);
			}
		}
		while (!q.isEmpty()) {
			String w = q.remove();
			if (w.indexOf("aaa") != -1 && w.indexOf("bbb") != -1)
				return d.get(w);
			for (int i = 0; i < w.length() - 1; i++) {
				String w2 = w.substring(0, i) + w.charAt(i + 1) + w.charAt(i) + w.substring(i + 2);
				if (!d.containsKey(w2)) {
					d.put(w2, d.get(w) + 1);
					q.add(w2);
				}
			}
		}
		return 0;
	}
}

Analysis

expand all Example tests

▶

example1
First example test.

✔

0.072 s

▶

example2
Second example test.

✔

0.004 s

▶

example3
Third example test.

✔

0.004 s

▶

example4
Fourth example test.

✔

0.004 s

Code: 11:14:41 UTC, java11, final, score: 100

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

class Solution {
	public int solution(String S) {

		int[] count = new int[] {0, 0};
		int[][] pos = new int[2][S.length()];
		int[] poscount = new int[] {0, 0};

		boolean[] has3 = new boolean[] {false, false};

		for (int i = 0; i < S.length(); i++) {
			int n = S.charAt(i) - 'a';
			count[n]++;
			if (i > 1 && !has3[n])
				has3[n] = (S.charAt(i) == S.charAt(i - 1) && S.charAt(i) == S.charAt(i - 2));
			pos[n][poscount[n]++] = i;
		}

		if (count[0] < 3 || count[1] < 3)
			return -1;

		for (int i = 0; i < 2; i++)
			if (has3[i]) {
				int ans = S.length();
				int i2 = i == 0 ? 1 : 0;
				for (int j = 0; j < poscount[i2] - 2; j++)
					ans = Math.min(ans, pos[i2][j + 2] - pos[i2][j] - 2);
				return ans;
			}

		Map<String, Integer> d = new HashMap<>();
		Queue<String> q = new LinkedList<>();
		for (int i = 0; i < S.length(); i++) {
			String w = i + 8 < S.length() ? S.substring(i, i + 8) : S.substring(i);
			if (!d.containsKey(w)) {
				d.put(w, 0);
				q.add(w);
			}
		}
		while (!q.isEmpty()) {
			String w = q.remove();
			if (w.indexOf("aaa") != -1 && w.indexOf("bbb") != -1)
				return d.get(w);
			for (int i = 0; i < w.length() - 1; i++) {
				String w2 = w.substring(0, i) + w.charAt(i + 1) + w.charAt(i) + w.substring(i + 2);
				if (!d.containsKey(w2)) {
					d.put(w2, d.get(w) + 1);
					q.add(w2);
				}
			}
		}
		return 0;
	}
}

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(N)

expand all Example tests

▶

example1
First example test.

✔

0.072 s

▶

example2
Second example test.

✔

0.004 s

▶

example3
Third example test.

✔

0.004 s

▶

example4
Fourth example test.

✔

0.004 s

expand all Correctness tests

▶

ans_2
Short test with result -1 or 2. N <= 10.

✔

0.004 s

0.076 s

0.072 s

10.

0.076 s

11.

0.072 s

12.

0.072 s

13.

0.004 s

14.

0.004 s

15.

0.076 s

16.

0.072 s

▶

ans03
Short test with result 0 or 3. N <= 10.

✔

0.080 s

0.076 s

0.004 s

10.

0.004 s

11.

0.004 s

12.

0.004 s

13.

0.076 s

14.

0.076 s

15.

0.004 s

16.

0.004 s

▶

ans14
Short test with result 1 or 4. N <= 16.

✔

0.080 s

0.004 s

10.

0.004 s

11.

0.072 s

12.

0.072 s

13.

0.076 s

14.

0.072 s

15.

0.004 s

16.

0.004 s

17.

0.004 s

18.

0.004 s

▶

ans5
Short test with result 5. N <= 10.

✔

0.072 s

0.076 s

0.004 s

▶

random
Random test cases. N <= 10.

✔

0.004 s

0.072 s

▶

max_answer
Number of required swaps is maximum possible. N <= 8.

✔

0.004 s

expand all Performance tests

▶

medium_big_answer
Answer is bigger than 4. N <= 50. Score x 2.

✔

0.004 s

▶

medium_pattern
S contains repeating pattern. N <= 100. Score x 2.

✔

0.072 s

0.080 s

0.076 s

0.080 s

0.076 s

0.004 s

10.

0.004 s

11.

0.004 s

12.

0.004 s

▶

large_big_answer
Answer is bigger than 4. Score x 2.

✔

0.120 s

0.116 s

0.120 s

0.124 s

▶

large_no_three_consecutive
No three consecutive letters in S are equal. Score x 2.

✔

0.604 s

0.596 s

0.080 s

0.608 s

0.080 s

▶

large_perf
Big performance package. Score x 2.

✔

0.592 s

0.584 s

0.580 s

0.604 s

0.576 s

0.588 s

0.080 s

0.144 s

0.168 s

10.

0.144 s

11.

0.164 s