Test results - Codility

Tasks Details

medium

1. LargestString

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

Task Score

63%

Correctness

100%

Performance

20%

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:

function solution(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 JavaScript

Time spent on task 7 minutes

Notes

not defined yet

Code: 18:51:21 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: 18:51:45 UTC, js, 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

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(S) {
    // write your code in JavaScript (Node.js 8.9.4)
    return S.reduce()
}

let ans;
function solution(S) {
    // write your code in JavaScript (Node.js 8.9.4)
    let a = S.replace(/abb/g, 'baa');
    if (S == a) {
        ans = a;
    }else{
        solution(a)
    }
    return ans;
}

Code: 18:51:55 UTC, js, 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

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(S) {
    // write your code in JavaScript (Node.js 8.9.4)
    return
}

let ans;
function solution(S) {
    // write your code in JavaScript (Node.js 8.9.4)
    let a = S.replace(/abb/g, 'baa');
    if (S == a) {
        ans = a;
    }else{
        solution(a)
    }
    return ans;
}

Code: 18:52:19 UTC, js, 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

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(S) {
    // write your code in JavaScript (Node.js 8.9.4)
    return
}

let ans;
function solution(S) {
    // write your code in JavaScript (Node.js 8.9.4)
    let a = S.replace(/abb/g, 'baa');
    if (S == a) {
        ans = a;
    }else{
        solution(a)
    }
    return ans;
    
    while ()
}

Code: 18:52:32 UTC, js, 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

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(S) {
    // write your code in JavaScript (Node.js 8.9.4)
    return
}

let ans;
function solution(S) {
    // write your code in JavaScript (Node.js 8.9.4)
    let a = S.replace(/abb/g, 'baa');
    if (S == a) {
        ans = a;
    }else{
        solution(a)
    }
    return ans;
    
    while (ans == S){
        
    }
}

Code: 18:52:53 UTC, js, 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

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(S) {
    // write your code in JavaScript (Node.js 8.9.4)
    return
}

let ans;
function solution(S) {
    // write your code in JavaScript (Node.js 8.9.4)
    let a = 
    if (S == a) {
        ans = a;
    }else{
        solution(a)
    }
    return ans;
    
    while (ans == S){
        S.replace(/abb/g, 'baa');
    }
}

Code: 18:53:08 UTC, js, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

let ans;
function solution(S) {
    // write your code in JavaScript (Node.js 8.9.4)
    while (ans == S){
        S.replace(/abb/g, 'baa');
    }
}

Code: 18:53:24 UTC, js, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

let ans;
function solution(S) {
    // write your code in JavaScript (Node.js 8.9.4)
    while (ans != S){
        ans = S.replace(/abb/g, 'baa');
    }
    
}

Code: 18:53:35 UTC, js, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

let ans;
function solution(S) {
    // write your code in JavaScript (Node.js 8.9.4)
    while (ans != S){
        ans = S.replace(/abb/g, 'baa');
    }
    return ans;
}

Code: 18:53:37 UTC, js, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

let ans;
function solution(S) {
    // write your code in JavaScript (Node.js 8.9.4)
    while (ans != S){
        ans = S.replace(/abb/g, 'baa');
    }
    return ans;
}

Analysis

expand all Example tests

▶

example1
First example test.

✘

TIMEOUT ERROR
Killed. Hard limit reached: 5.000 sec.

5.000 s

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

▶

example2
Second example test.

✘

TIMEOUT ERROR
Killed. Hard limit reached: 5.000 sec.

5.000 s

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

▶

example3
Third example test.

✔

0.072 s

Code: 18:54:29 UTC, js, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

let ans;
function solution(S) {
    // write your code in JavaScript (Node.js 8.9.4)
    
    while (ans != S){
        ans = S.replace(/abb/g, 'baa');
    }
    return ans;
}

Code: 18:54:39 UTC, js, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

let ans;
function solution(S) {
    // write your code in JavaScript (Node.js 8.9.4)
    let a;
    while (ans != S){
        ans = S.replace(/abb/g, 'baa');
    }
    return ans;
}

Code: 18:55:43 UTC, js, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

let ans;
function solution(S) {
    // write your code in JavaScript (Node.js 8.9.4)
    let a;
    while (ans != ans){
        ans = S.replace(/abb/g, 'baa');
    }
    return ans;
}

Code: 18:56:02 UTC, js, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

let ans;
function solution(S) {
    // write your code in JavaScript (Node.js 8.9.4)
    let a;
    while (ans != ans.replace(/abb/g, 'baa')){
        ans = S.replace(/abb/g, 'baa');
    }
    return ans;
}

Code: 18:56:06 UTC, js, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

let ans;
function solution(S) {
    // write your code in JavaScript (Node.js 8.9.4)
    let a;
    while (ans != ans.replace(/abb/g, 'baa')){
        ans = S.replace(/abb/g, 'baa');
    }
    return ans;
}

Analysis

expand all Example tests

▶

example1
First example test.

✘

RUNTIME ERROR
tested program terminated with exit code 1

0.072 s

RUNTIME ERROR, tested program terminated with exit code 1

stderr:

TypeError: Cannot read property 'replace' of undefined
    at solution (solution.js:8:23)
    at solutionWrapper (/tmp/exec.js:394:28)
    at Promise.resolve.then (/tmp/exec.js:420:24)
    at <anonymous>
    at process._tickCallback (internal/process/next_tick.js:188:7)
    at Function.Module.runMain (module.js:686:11)
    at startup (bootstrap_node.js:187:16)
    at bootstrap_node.js:608:3

▶

example2
Second example test.

✘

RUNTIME ERROR
tested program terminated with exit code 1

0.072 s

RUNTIME ERROR, tested program terminated with exit code 1

stderr:

TypeError: Cannot read property 'replace' of undefined
    at solution (solution.js:8:23)
    at solutionWrapper (/tmp/exec.js:394:28)
    at Promise.resolve.then (/tmp/exec.js:420:24)
    at <anonymous>
    at process._tickCallback (internal/process/next_tick.js:188:7)
    at Function.Module.runMain (module.js:686:11)
    at startup (bootstrap_node.js:187:16)
    at bootstrap_node.js:608:3

▶

example3
Third example test.

✘

RUNTIME ERROR
tested program terminated with exit code 1

0.072 s

RUNTIME ERROR, tested program terminated with exit code 1

stderr:

TypeError: Cannot read property 'replace' of undefined
    at solution (solution.js:8:23)
    at solutionWrapper (/tmp/exec.js:394:28)
    at Promise.resolve.then (/tmp/exec.js:420:24)
    at <anonymous>
    at process._tickCallback (internal/process/next_tick.js:188:7)
    at Function.Module.runMain (module.js:686:11)
    at startup (bootstrap_node.js:187:16)
    at bootstrap_node.js:608:3

Code: 18:56:32 UTC, js, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

let ans;
function solution(S) {
    // write your code in JavaScript (Node.js 8.9.4)
    ans = ;
    while (ans != ans.replace(/abb/g, 'baa')){
        ans = S.replace(/abb/g, 'baa');
    }
    return ans;
}

Code: 18:56:39 UTC, js, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

let ans;
function solution(S) {
    // write your code in JavaScript (Node.js 8.9.4)
    ans = S;
    while (ans != ans.replace(/abb/g, 'baa')){
        ans = S.replace(/abb/g, 'baa');
    }
    return ans;
}

Analysis

expand all Example tests

▶

example1
First example test.

✘

TIMEOUT ERROR
Killed. Hard limit reached: 5.000 sec.

5.000 s

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

▶

example2
Second example test.

✘

TIMEOUT ERROR
Killed. Hard limit reached: 5.000 sec.

5.000 s

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

▶

example3
Third example test.

✔

0.072 s

Code: 18:57:28 UTC, js, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

let ans;
function solution(S) {
    // write your code in JavaScript (Node.js 8.9.4)
    ans = S;
    while (ans = ans.replace(/abb/g, 'baa')){
        ans = S.replace(/abb/g, 'baa');
    }
    return ans;
}

Code: 18:57:30 UTC, js, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

let ans;
function solution(S) {
    // write your code in JavaScript (Node.js 8.9.4)
    ans = S;
    while (ans == ans.replace(/abb/g, 'baa')){
        ans = S.replace(/abb/g, 'baa');
    }
    return ans;
}

Analysis

expand all Example tests

▶

example1
First example test.

✘

WRONG ANSWER
got ababb expected baaaa

0.072 s

WRONG ANSWER, got ababb expected baaaa

▶

example2
Second example test.

✘

WRONG ANSWER
got abbbabb expected babaaaa

0.068 s

WRONG ANSWER, got abbbabb expected babaaaa

▶

example3
Third example test.

✘

TIMEOUT ERROR
Killed. Hard limit reached: 5.000 sec.

5.000 s

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

Code: 18:57:58 UTC, js, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

let ans;
function solution(S) {
    // write your code in JavaScript (Node.js 8.9.4)
    ans = S;
    while (ans == ans.replace(/abb/g, 'baa')){
        ans = a.replace(/abb/g, 'baa');
    }
    return ans;
}

Code: 18:58:08 UTC, js, verify, result: Passed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

let ans;
function solution(S) {
    // write your code in JavaScript (Node.js 8.9.4)
    ans = S;
    while (ans != ans.replace(/abb/g, 'baa')){
        ans = ans.replace(/abb/g, 'baa');
    }
    return ans;
}

Analysis

expand all Example tests

▶

example1
First example test.

✔

0.072 s

▶

example2
Second example test.

✔

0.072 s

▶

example3
Third example test.

✔

0.072 s

Code: 18:58:13 UTC, js, verify, result: Passed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

let ans;
function solution(S) {
    // write your code in JavaScript (Node.js 8.9.4)
    ans = S;
    while (ans != ans.replace(/abb/g, 'baa')){
        ans = ans.replace(/abb/g, 'baa');
    }
    return ans;
}

Analysis

expand all Example tests

▶

example1
First example test.

✔

0.072 s

▶

example2
Second example test.

✔

0.072 s

▶

example3
Third example test.

✔

0.072 s

Code: 18:58:16 UTC, js, final, score: 63

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

let ans;
function solution(S) {
    // write your code in JavaScript (Node.js 8.9.4)
    ans = S;
    while (ans != ans.replace(/abb/g, 'baa')){
        ans = ans.replace(/abb/g, 'baa');
    }
    return ans;
}

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.068 s

▶

example2
Second example test.

✔

0.068 s

▶

example3
Third example test.

✔

0.072 s

expand all Correctness tests

▶

simple
Simple small test. N <= 10.

✔

0.072 s

0.068 s

0.072 s

0.068 s

▶

small
Small size. N <= 2.

✔

0.068 s

▶

overlap
Overlapping substitutions. N <= 10.

✔

0.068 s

▶

alternating
Alternating string. N <= 15.

✔

0.068 s

▶

monotone
Monotone string. N <= 15.

✔

0.068 s

0.072 s

▶

small_random
Small random tests. N = 50.

✔

0.068 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.068 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.

0.076 s

▶

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.068 s

▶

random_big
Random big string. N = 100,000.

✔

0.088 s

0.084 s

0.092 s