Test results - Codility

Tasks Details

medium

1. LargestString

Find the alphabetically largest string that can be obtained by performing some substitutions.

Task Score

54%

Correctness

100%

Performance

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

Solution

Programming language used Java 21

Time spent on task 1 minutes

Notes

not defined yet

Code: 03:51:12 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 String solution(String S) {
        // write your code in Java SE 8
    }
}

Code: 03:51:33 UTC, java, 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

// 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 func solution(_ S : inout String) -> String {
  // write your code in Swift 4.2.1 (Linux)
  var hasFound = true
  var res = Array(S)
  // Do iterate until every transformation
  while hasFound && res.count > 2 {
    hasFound = false
    for index in 0..<res.count-2 {
      if res[index] == "a" && res[index+1] == "b" && res[index+2] == "b" {
        hasFound = true
        res[index] = "b"
        res[index+1] = "a"
        res[index+2] = "a"
        break;
      }
    }
  }
  
  return String(res)
}
}

Code: 03:51:44 UTC, swift4, 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

import Foundation
import Glibc

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

public func solution(_ S : inout String) -> String {
  // write your code in Swift 4.2.1 (Linux)
  var hasFound = true
  var res = Array(S)
  // Do iterate until every transformation
  while hasFound && res.count > 2 {
    hasFound = false
    for index in 0..<res.count-2 {
      if res[index] == "a" && res[index+1] == "b" && res[index+2] == "b" {
        hasFound = true
        res[index] = "b"
        res[index+1] = "a"
        res[index+2] = "a"
        break;
      }
    }
  }
  
  return String(res)
}

Code: 03:51:44 UTC, swift4, 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

import Foundation
import Glibc

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

public func solution(_ S : inout String) -> String {
  // write your code in Swift 4.2.1 (Linux)
  var hasFound = true
  var res = Array(S)
  // Do iterate until every transformation
  while hasFound && res.count > 2 {
    hasFound = false
    for index in 0..<res.count-2 {
      if res[index] == "a" && res[index+1] == "b" && res[index+2] == "b" {
        hasFound = true
        res[index] = "b"
        res[index+1] = "a"
        res[index+2] = "a"
        break;
      }
    }
  }
  
  return String(res)
}

Analysis

expand all Example tests

▶

example1
First example test.

✔

0.028 s

▶

example2
Second example test.

✔

0.028 s

▶

example3
Third example test.

✔

0.028 s

Code: 03:51:53 UTC, swift4, 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

import Foundation
import Glibc

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

public func solution(_ S : inout String) -> String {
  // write your code in Swift 4.2.1 (Linux)
  var hasFound = true
  var res = Array(S)
  // Do iterate until every transformation
  while hasFound && res.count > 2 {
    hasFound = false
    for index in 0..<res.count-2 {
      if res[index] == "a" && res[index+1] == "b" && res[index+2] == "b" {
        hasFound = true
        res[index] = "b"
        res[index+1] = "a"
        res[index+2] = "a"
        break;
      }
    }
  }
  
  return String(res)
}

Analysis

expand all Example tests

▶

example1
First example test.

✔

0.032 s

▶

example2
Second example test.

✔

0.028 s

▶

example3
Third example test.

✔

0.028 s

Code: 03:52:00 UTC, swift4, final, score: 54

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

import Foundation
import Glibc

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

public func solution(_ S : inout String) -> String {
  // write your code in Swift 4.2.1 (Linux)
  var hasFound = true
  var res = Array(S)
  // Do iterate until every transformation
  while hasFound && res.count > 2 {
    hasFound = false
    for index in 0..<res.count-2 {
      if res[index] == "a" && res[index+1] == "b" && res[index+2] == "b" {
        hasFound = true
        res[index] = "b"
        res[index+1] = "a"
        res[index+2] = "a"
        break;
      }
    }
  }
  
  return String(res)
}

Analysis summary

The following issues have been detected: timeout errors.

Analysis

Detected time complexity:

O(N**2)

expand all Example tests

▶

example1
First example test.

✔

0.032 s

▶

example2
Second example test.

✔

0.028 s

▶

example3
Third example test.

✔

0.028 s

expand all Correctness tests

▶

simple
Simple small test. N <= 10.

✔

0.028 s

▶

small
Small size. N <= 2.

✔

0.028 s

▶

overlap
Overlapping substitutions. N <= 10.

✔

0.028 s

▶

alternating
Alternating string. N <= 15.

✔

0.028 s

▶

monotone
Monotone string. N <= 15.

✔

0.028 s

▶

small_random
Small random tests. N = 50.

✔

0.028 s

expand all Performance tests

▶

big_simple
Simple big test. N = 100,000. Score x 3.

✘

TIMEOUT ERROR
Killed. Hard limit reached: 6.000 sec.

0.056 s

6.000 s

TIMEOUT ERROR, Killed. Hard limit reached: 6.000 sec.

6.000 s

TIMEOUT ERROR, Killed. Hard limit reached: 6.000 sec.

6.000 s

TIMEOUT ERROR, Killed. Hard limit reached: 6.000 sec.

6.000 s

TIMEOUT ERROR, Killed. Hard limit reached: 6.000 sec.

6.000 s

TIMEOUT ERROR, Killed. Hard limit reached: 6.000 sec.

▶

big_monotone
Monotone string. N = 100,000.

✘

TIMEOUT ERROR
Killed. Hard limit reached: 6.000 sec.

6.000 s

TIMEOUT ERROR, Killed. Hard limit reached: 6.000 sec.

0.056 s

▶

random_big
Random big string. N = 100,000.

✘

TIMEOUT ERROR
Killed. Hard limit reached: 6.000 sec.

6.000 s

TIMEOUT ERROR, Killed. Hard limit reached: 6.000 sec.

6.000 s

TIMEOUT ERROR, Killed. Hard limit reached: 6.000 sec.

6.000 s

TIMEOUT ERROR, Killed. Hard limit reached: 6.000 sec.

6.000 s

TIMEOUT ERROR, Killed. Hard limit reached: 6.000 sec.

6.000 s

TIMEOUT ERROR, Killed. Hard limit reached: 6.000 sec.