Tasks Details
medium
Find the alphabetically largest string that can be obtained by performing some substitutions.
Task Score
54%
Correctness
100%
Performance
0%
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:
func Solution(S string) string
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'.
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Go
Time spent on task 27 minutes
Notes
not defined yet
Code: 20:08:33 UTC,
java,
autosave
Code: 20:09:06 UTC,
go,
autosave
Code: 20:16:11 UTC,
go,
autosave
Code: 20:17:09 UTC,
go,
autosave
Code: 20:17:38 UTC,
go,
autosave
Code: 20:18:09 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) string {
// write your code in Go 1.4
for i,v := range S {
if v =
}
}
Code: 20:18:19 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) string {
// write your code in Go 1.4
for i,v := range S {
if v == rune()
}
}
Code: 20:19:12 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) string {
// write your code in Go 1.4
for i,v := range S {
if v == rune(a)
}
}
Code: 20:19:23 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) string {
// write your code in Go 1.4
for i,v := range S {
if v == rune("a")
}
}
Code: 20:19:54 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) string {
// write your code in Go 1.4
for i,v := range S {
if v == rune("a"){}
}
}
Code: 20:20:07 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) string {
// write your code in Go 1.4
for i,v := range S {
if v == rune("a") && r{
}
}
}
Code: 20:20:26 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) string {
// write your code in Go 1.4
for i,v := range S {
if v == rune("a") && i < len(S){
}
}
}
Code: 20:20:51 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) string {
// write your code in Go 1.4
for i,v := range S {
if v == rune("a") && i < len(S)-2{
}
}
}
Code: 20:21:32 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) string {
// write your code in Go 1.4
for i,v := range S {
if v == rune("a") && i < len(S)-2 {
}
}
}
Code: 20:21:51 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) string {
// write your code in Go 1.4
for i,v := range S {
if v == rune("a") && i < len(S)-2 && S[i+1] =={
}
}
}
Code: 20:22:07 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) string {
// write your code in Go 1.4
for i,v := range S {
if v == rune("a") && i < len(S)-2 && S[i+1] =="b" && {
}
}
}
Code: 20:22:19 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) string {
// write your code in Go 1.4
for i,v := range S {
if v == rune("a") && i < len(S)-2 && S[i+1] =="b" && S[i+1] == {
}
}
}
Code: 20:22:31 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) string {
// write your code in Go 1.4
for i,v := range S {
if v == rune("a") && i < len(S)-2 && S[i+1] =="b" && S[i+2] == {
}
}
}
Code: 20:22:41 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) string {
// write your code in Go 1.4
for i,v := range S {
if v == rune("a") && i < len(S)-2 && S[i+1] =="b" && S[i+2] =="b" {
}
}
}
Code: 20:22:54 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) string {
// write your code in Go 1.4
for i,v := range S {
if v == rune("a") && i < len(S)-2 && S[i+1] ==rune("b" && S[i+2] =="b" {
}
}
}
Code: 20:23:07 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) string {
// write your code in Go 1.4
for i,v := range S {
if v == rune("a") && i < len(S)-2 && S[i+1] ==rune("b") && S[i+2] ==rune("b") {
}
}
}
Code: 20:23:51 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) string {
// write your code in Go 1.4
for i,v := range S {
if v == rune("a") && i < len(S)-2 && S[i+1] ==rune("b") && S[i+2] ==rune("b") {
}
}
}
Code: 20:24:16 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) string {
// write your code in Go 1.4
for i,v := range S {
if v == rune("a") && i < len(S)-2 && S[i+1] ==rune("b") && S[i+2] ==rune("b") {
S[]
}
}
}
Code: 20:24:28 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) string {
// write your code in Go 1.4
for i,v := range S {
if v == rune("a") && i < len(S)-2 && S[i+1] ==rune("b") && S[i+2] ==rune("b") {
S[i] =
}
}
}
Code: 20:27:12 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) string {
// write your code in Go 1.4
for i,v := range S {
if v == rune("a") && i < len(S)-2 && S[i+1] ==rune("b") && S[i+2] ==rune("b") {
S[i] =
}
}
}
Code: 20:27:32 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) string {
// write your code in Go 1.4
s := []rune(S)
for i,v := range S {
if v == rune("a") && i < len(S)-2 && S[i+1] ==rune("b") && S[i+2] ==rune("b") {
S[i] =
}
}
}
Code: 20:27:42 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) string {
// write your code in Go 1.4
s := []rune(S)
for i,v := range s {
if v == rune("a") && i < len(S)-2 && S[i+1] ==rune("b") && S[i+2] ==rune("b") {
s[i] =
}
}
}
Code: 20:28:07 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) string {
// write your code in Go 1.4
s := []rune(S)
for i,v := range s {
if v == rune("a") && i < len(S)-2 && S[i+1] ==rune("b") && S[i+2] ==rune("b") {
s[i] = rune("b")
}
}
}
Code: 20:28:18 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) string {
// write your code in Go 1.4
s := []rune(S)
for i,v := range s {
if v == rune("a") && i < len(S)-2 && S[i+1] ==rune("b") && S[i+2] ==rune("b") {
s[i] = rune("b")
s[i] = rune("b")
}
}
}
Code: 20:28:28 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) string {
// write your code in Go 1.4
s := []rune(S)
for i,v := range s {
if v == rune("a") && i < len(S)-2 && S[i+1] ==rune("b") && S[i+2] ==rune("b") {
s[i] = rune("b")
s[i+1] = rune("a")
}
}
}
Code: 20:28:40 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) string {
// write your code in Go 1.4
s := []rune(S)
for i,v := range s {
if v == rune("a") && i < len(S)-2 && S[i+1] ==rune("b") && S[i+2] ==rune("b") {
s[i] = rune("b")
s[i+1] = rune("a")
s[i+2] = rune("a")
}
}
}
Code: 20:28:50 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) string {
// write your code in Go 1.4
s := []rune(S)
for i,v := range s {
if v == rune("a") && i < len(S)-2 && S[i+1] ==rune("b") && S[i+2] ==rune("b") {
s[i] = rune("b")
s[i+1] = rune("a")
s[i+2] = rune("a")
return
}
}
}
Code: 20:29:00 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) string {
// write your code in Go 1.4
s := []rune(S)
for i,v := range s {
if v == rune("a") && i < len(S)-2 && S[i+1] ==rune("b") && S[i+2] ==rune("b") {
s[i] = rune("b")
s[i+1] = rune("a")
s[i+2] = rune("a")
return Solution(S)
}
}
}
Code: 20:29:20 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) string {
// write your code in Go 1.4
s := []rune(S)
for i,v := range s {
if v == rune("a") && i < len(S)-2 && S[i+1] ==rune("b") && S[i+2] ==rune("b") {
s[i] = rune("b")
s[i+1] = rune("a")
s[i+2] = rune("a")
return Solution(string(s))
}
}
}
Code: 20:29:39 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) string {
// write your code in Go 1.4
s := []rune(S)
for i,v := range s {
if v == rune("a") && i < len(S)-2 && S[i+1] ==rune("b") && S[i+2] ==rune("b") {
s[i] = rune("b")
s[i+1] = rune("a")
s[i+2] = rune("a")
return Solution(string(s))
}
}
return string
}
Code: 20:29:46 UTC,
go,
verify,
result: Failed
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) string {
// write your code in Go 1.4
s := []rune(S)
for i,v := range s {
if v == rune("a") && i < len(S)-2 && S[i+1] ==rune("b") && S[i+2] ==rune("b") {
s[i] = rune("b")
s[i+1] = rune("a")
s[i+2] = rune("a")
return Solution(string(s))
}
}
return string(s)
}
Analysis
Compile error
# solution workspace/src/solution/solution.go:14: cannot convert "a" to type rune workspace/src/solution/solution.go:14: cannot convert "a" (type string) to type rune workspace/src/solution/solution.go:14: invalid operation: v == "a" (mismatched types rune and string) workspace/src/solution/solution.go:14: cannot convert "b" to type rune workspace/src/solution/solution.go:14: cannot convert "b" (type string) to type rune workspace/src/solution/solution.go:14: invalid operation: S[i + 1] == "b" (mismatched types uint8 and string) workspace/src/solution/solution.go:14: cannot convert "b" to type rune workspace/src/solution/solution.go:14: cannot convert "b" (type string) to type rune workspace/src/solution/solution.go:14: invalid operation: S[i + 2] == "b" (mismatched types uint8 and string) workspace/src/solution/solution.go:15: cannot convert "b" to type rune workspace/src/solution/solution.go:15: too many errors
Code: 20:31:27 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) string {
// write your code in Go 1.4
s := []rune(S)
for i,v := range s {
if v == && i < len(S)-2 && S[i+1] ==rune("b") && S[i+2] ==rune("b") {
s[i] = rune("b")
s[i+1] = rune("a")
s[i+2] = rune("a")
return Solution(string(s))
}
}
return string(s)
}
Code: 20:31:41 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) string {
// write your code in Go 1.4
s := []rune(S)
for i,v := range s {
if v == 'a' && i < len(S)-2 && S[i+1] =='b' && S[i+2] ==rune("b") {
s[i] = rune("b")
s[i+1] = rune("a")
s[i+2] = rune("a")
return Solution(string(s))
}
}
return string(s)
}
Code: 20:31:56 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) string {
// write your code in Go 1.4
s := []rune(S)
for i,v := range s {
if v == 'a' && i < len(S)-2 && S[i+1] =='b' && S[i+2] =='b' {
s[i] = 'b'
s[i+1] = rune("a")
s[i+2] = rune("a")
return Solution(string(s))
}
}
return string(s)
}
Code: 20:32:08 UTC,
go,
verify,
result: Passed
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) string {
// write your code in Go 1.4
s := []rune(S)
for i,v := range s {
if v == 'a' && i < len(S)-2 && S[i+1] =='b' && S[i+2] =='b' {
s[i] = 'b'
s[i+1] = 'a'
s[i+2] = 'a'
return Solution(string(s))
}
}
return string(s)
}
Analysis
Code: 20:32:08 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) string {
// write your code in Go 1.4
s := []rune(S)
for i,v := range s {
if v == 'a' && i < len(S)-2 && S[i+1] =='b' && S[i+2] =='b' {
s[i] = 'b'
s[i+1] = 'a'
s[i+2] = 'a'
return Solution(string(s))
}
}
return string(s)
}
Code: 20:32:18 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) string {
// write your code in Go 1.4
s := []rune(S)
for i,v := range s {
if v == 'a' && i < len(s)-2 && S[i+1] =='b' && S[i+2] =='b' {
s[i] = 'b'
s[i+1] = 'a'
s[i+2] = 'a'
return Solution(string(s))
}
}
return string(s)
}
Code: 20:32:27 UTC,
go,
verify,
result: Passed
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) string {
// write your code in Go 1.4
s := []rune(S)
for i,v := range s {
if v == 'a' && i < len(s)-2 && s[i+1] =='b' && s[i+2] =='b' {
s[i] = 'b'
s[i+1] = 'a'
s[i+2] = 'a'
return Solution(string(s))
}
}
return string(s)
}
Analysis
Code: 20:34:23 UTC,
go,
verify,
result: Passed
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) string {
// write your code in Go 1.4
s := []rune(S)
for i,v := range s {
if v == 'a' && i < len(s)-2 && s[i+1] =='b' && s[i+2] =='b' {
s[i] = 'b'
s[i+1] = 'a'
s[i+2] = 'a'
return Solution(string(s))
}
}
return string(s)
}
Analysis
Code: 20:34:29 UTC,
go,
final,
score:
54
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) string {
// write your code in Go 1.4
s := []rune(S)
for i,v := range s {
if v == 'a' && i < len(s)-2 && s[i+1] =='b' && s[i+2] =='b' {
s[i] = 'b'
s[i+1] = 'a'
s[i+2] = 'a'
return Solution(string(s))
}
}
return string(s)
}
Analysis summary
The following issues have been detected: timeout errors.
Analysis
Detected time complexity:
O(N**2)
expand all
Correctness tests
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
4.
0.001 s
OK
5.
0.001 s
OK
1.
0.001 s
OK
2.
0.001 s
OK
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
4.
0.001 s
OK
5.
0.001 s
OK
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
4.
0.001 s
OK
5.
0.001 s
OK
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
4.
0.001 s
OK
5.
0.001 s
OK
6.
0.001 s
OK
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
4.
0.001 s
OK
5.
0.001 s
OK
expand all
Performance tests
big_simple
Simple big test. N = 100,000. Score x 3.
Simple big test. N = 100,000. Score x 3.
✘
TIMEOUT ERROR
Killed. Hard limit reached: 6.000 sec.
Killed. Hard limit reached: 6.000 sec.
1.
0.004 s
OK
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.
6.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 6.000 sec.
5.
6.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 6.000 sec.
6.
6.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 6.000 sec.
1.
6.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 6.000 sec.
2.
0.004 s
OK
3.
0.004 s
OK
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.
6.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 6.000 sec.
5.
6.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 6.000 sec.