Tasks Details
medium
Given a string, find the length of the longest substring in which every character appears an even number of times.
Task Score
50%
Correctness
100%
Performance
20%
John takes computer security very seriously, so he has picked a very long password to secure his files. However, although the password is very strong, it is also hard to memorize.
John decides to create a new password which is easier to remember. Therefore, it must fulfill certain requirements: he wants each character (digit or letter) to appear in the new password an even number of times (possibly zero). Also, since he is so proud of his original password, he wants the new password to be a contiguous substring of the original password.
John has trouble finding such a substring. Help him by finding, for a given string, the length of the longest substring that fulfills the requirements set out above.
Write a function:
func Solution(S string) int
that, given a non-empty string S consisting of N characters, returns the length of the longest contiguous substring (possibly empty) of string S in which every character occurs an even number of times.
For example, given S = "6daa6ccaaa6d", the function should return 8. The longest valid password taken from S is "a6ccaaa6"; it contains four letters a, and two each of the digit 6 and letter c. Any longer substring must contain either five letters a or one letter d. Given S = "abca", the function should return 0 (note that aa is not a contiguous substring of S).
Write an efficient algorithm for the following assumptions:
- the length of string S is within the range [1..100,000];
- S consists only of lowercase letters and digits.
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Go
Time spent on task 62 minutes
Notes
not defined yet
Code: 14:39:49 UTC,
java,
autosave
Code: 14:39:59 UTC,
go,
autosave
Code: 15:26:52 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) int {
// write your code in Go 1.4
}
func isStringCharactersEven(s string) bool {
r := []rune(s)
sort.Slice(r, func(i, j int) bool {
return r[i] < r[j]
})
prev := 0
for i := 0; i < len(r); i++ {
if i%2 == 1 {
if int(r[i]) != prev {
return false
}
} else {
prev = int(r[i])
}
}
return true
}
Code: 15:27:02 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
import (
"sort"
)
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) int {
// write your code in Go 1.4
}
func isStringCharactersEven(s string) bool {
r := []rune(s)
sort.Slice(r, func(i, j int) bool {
return r[i] < r[j]
})
prev := 0
for i := 0; i < len(r); i++ {
if i%2 == 1 {
if int(r[i]) != prev {
return false
}
} else {
prev = int(r[i])
}
}
return true
}
Code: 15:27:04 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
import (
"sort"
)
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) int {
// write your code in Go 1.4
for i := len(S); i > 0; i-- {
if i%2 != 0 {
continue
}
for j := 0; j < len(S)-i; j++ {
substring := S[j:i]
if isStringCharactersEven(substring) {
return len(substring)
}
}
}
return 0
}
func isStringCharactersEven(s string) bool {
r := []rune(s)
sort.Slice(r, func(i, j int) bool {
return r[i] < r[j]
})
prev := 0
for i := 0; i < len(r); i++ {
if i%2 == 1 {
if int(r[i]) != prev {
return false
}
} else {
prev = int(r[i])
}
}
return true
}
Code: 15:27:06 UTC,
go,
verify,
result: Failed
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
import (
"sort"
)
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) int {
// write your code in Go 1.4
for i := len(S); i > 0; i-- {
if i%2 != 0 {
continue
}
for j := 0; j < len(S)-i; j++ {
substring := S[j:i]
if isStringCharactersEven(substring) {
return len(substring)
}
}
}
return 0
}
func isStringCharactersEven(s string) bool {
r := []rune(s)
sort.Slice(r, func(i, j int) bool {
return r[i] < r[j]
})
prev := 0
for i := 0; i < len(r); i++ {
if i%2 == 1 {
if int(r[i]) != prev {
return false
}
} else {
prev = int(r[i])
}
}
return true
}
Analysis
Compile error
# solution workspace/src/solution/solution.go:30: undefined: sort.Slice
Code: 15:35:27 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
import (
"sort"
)
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) int {
// write your code in Go 1.4
for i := len(S); i > 0; i-- {
if i%2 != 0 {
continue
}
for j := 0; j <= len(S)-i; j++ {
substring := S[j : i+j]
if isStringCharactersEven(substring) {
return len(substring)
}
}
}
return 0
}
func isStringCharactersEven(s string) bool {
r := []rune(s)
sort.Slice(r, func(i, j int) bool {
return r[i] < r[j]
})
prev := 0
for i := 0; i < len(r); i++ {
if i%2 == 1 {
if int(r[i]) != prev {
return false
}
} else {
prev = int(r[i])
}
}
return true
}
Code: 15:35:29 UTC,
go,
verify,
result: Failed
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
import (
"sort"
)
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) int {
// write your code in Go 1.4
for i := len(S); i > 0; i-- {
if i%2 != 0 {
continue
}
for j := 0; j <= len(S)-i; j++ {
substring := S[j : i+j]
if isStringCharactersEven(substring) {
return len(substring)
}
}
}
return 0
}
func isStringCharactersEven(s string) bool {
r := []rune(s)
sort.Slice(r, func(i, j int) bool {
return r[i] < r[j]
})
prev := 0
for i := 0; i < len(r); i++ {
if i%2 == 1 {
if int(r[i]) != prev {
return false
}
} else {
prev = int(r[i])
}
}
return true
}
Analysis
Compile error
# solution workspace/src/solution/solution.go:30: undefined: sort.Slice
Code: 15:37:32 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
import (
"sort"
)
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) int {
// write your code in Go 1.4
for i := len(S); i > 0; i-- {
if i%2 != 0 {
continue
}
for j := 0; j <= len(S)-i; j++ {
substring := S[j : i+j]
if isStringCharactersEven(substring) {
return len(substring)
}
}
}
return 0
}
func isStringCharactersEven(s string) bool {
r := []rune(s)
sort.Slice(r, func(i, j int) bool {
return r[i] < r[j]
})
prev := 0
for i := 0; i < len(r); i++ {
if i%2 == 1 {
if int(r[i]) != prev {
return false
}
} else {
prev = int(r[i])
}
}
return true
}
// ByRune is Type of rune array
type ByRune []rune
func (r ByRune) Len() int { return len(r) }
func (r ByRune) Swap(i, j int) { r[i], r[j] = r[j], r[i] }
func (r ByRune) Less(i, j int) bool { return r[i] < r[j] }
Code: 15:37:39 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
import (
"sort"
)
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) int {
// write your code in Go 1.4
for i := len(S); i > 0; i-- {
if i%2 != 0 {
continue
}
for j := 0; j <= len(S)-i; j++ {
substring := S[j : i+j]
if isStringCharactersEven(substring) {
return len(substring)
}
}
}
return 0
}
func isStringCharactersEven(s string) bool {
r := []rune(s)
sort.Sort(r, func(i, j int) bool {
return r[i] < r[j]
})
prev := 0
for i := 0; i < len(r); i++ {
if i%2 == 1 {
if int(r[i]) != prev {
return false
}
} else {
prev = int(r[i])
}
}
return true
}
// ByRune is Type of rune array
type ByRune []rune
func (r ByRune) Len() int { return len(r) }
func (r ByRune) Swap(i, j int) { r[i], r[j] = r[j], r[i] }
func (r ByRune) Less(i, j int) bool { return r[i] < r[j] }
Code: 15:37:40 UTC,
go,
verify,
result: Failed
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
import (
"sort"
)
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) int {
// write your code in Go 1.4
for i := len(S); i > 0; i-- {
if i%2 != 0 {
continue
}
for j := 0; j <= len(S)-i; j++ {
substring := S[j : i+j]
if isStringCharactersEven(substring) {
return len(substring)
}
}
}
return 0
}
func isStringCharactersEven(s string) bool {
r := []rune(s)
sort.Sort(r, func(i, j int) bool {
return r[i] < r[j]
})
prev := 0
for i := 0; i < len(r); i++ {
if i%2 == 1 {
if int(r[i]) != prev {
return false
}
} else {
prev = int(r[i])
}
}
return true
}
// ByRune is Type of rune array
type ByRune []rune
func (r ByRune) Len() int { return len(r) }
func (r ByRune) Swap(i, j int) { r[i], r[j] = r[j], r[i] }
func (r ByRune) Less(i, j int) bool { return r[i] < r[j] }
Analysis
Compile error
# solution workspace/src/solution/solution.go:32: too many arguments in call to sort.Sort
Code: 15:37:52 UTC,
go,
verify,
result: Failed
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
import (
"sort"
)
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) int {
// write your code in Go 1.4
for i := len(S); i > 0; i-- {
if i%2 != 0 {
continue
}
for j := 0; j <= len(S)-i; j++ {
substring := S[j : i+j]
if isStringCharactersEven(substring) {
return len(substring)
}
}
}
return 0
}
func isStringCharactersEven(s string) bool {
r := []rune(s)
sort.Sort(r)
prev := 0
for i := 0; i < len(r); i++ {
if i%2 == 1 {
if int(r[i]) != prev {
return false
}
} else {
prev = int(r[i])
}
}
return true
}
// ByRune is Type of rune array
type ByRune []rune
func (r ByRune) Len() int { return len(r) }
func (r ByRune) Swap(i, j int) { r[i], r[j] = r[j], r[i] }
func (r ByRune) Less(i, j int) bool { return r[i] < r[j] }
Analysis
Compile error
# solution workspace/src/solution/solution.go:30: cannot use r (type []rune) as type sort.Interface in argument to sort.Sort: []rune does not implement sort.Interface (missing Len method)
Code: 15:41:21 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
import (
"sort"
)
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) int {
// write your code in Go 1.4
for i := len(S); i > 0; i-- {
if i%2 != 0 {
continue
}
for j := 0; j <= len(S)-i; j++ {
substring := S[j : i+j]
if isStringCharactersEven(substring) {
return len(substring)
}
}
}
return 0
}
func isStringCharactersEven(s string) bool {
var r ByRune = []rune(s)
sort.Sort(r)
prev := 0
for i := 0; i < len(r); i++ {
if i%2 == 1 {
if int(r[i]) != prev {
return false
}
} else {
prev = int(r[i])
}
}
return true
}
// ByRune is Type of rune array
type ByRune []rune
func (r ByRune) Len() int { return len(r) }
func (r ByRune) Swap(i, j int) { r[i], r[j] = r[j], r[i] }
func (r ByRune) Less(i, j int) bool { return r[i] < r[j] }
Code: 15:41:23 UTC,
go,
verify,
result: Passed
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
import (
"sort"
)
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) int {
// write your code in Go 1.4
for i := len(S); i > 0; i-- {
if i%2 != 0 {
continue
}
for j := 0; j <= len(S)-i; j++ {
substring := S[j : i+j]
if isStringCharactersEven(substring) {
return len(substring)
}
}
}
return 0
}
func isStringCharactersEven(s string) bool {
var r ByRune = []rune(s)
sort.Sort(r)
prev := 0
for i := 0; i < len(r); i++ {
if i%2 == 1 {
if int(r[i]) != prev {
return false
}
} else {
prev = int(r[i])
}
}
return true
}
// ByRune is Type of rune array
type ByRune []rune
func (r ByRune) Len() int { return len(r) }
func (r ByRune) Swap(i, j int) { r[i], r[j] = r[j], r[i] }
func (r ByRune) Less(i, j int) bool { return r[i] < r[j] }
Analysis
Code: 15:41:44 UTC,
go,
verify,
result: Passed
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
import (
"sort"
)
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) int {
// write your code in Go 1.4
for i := len(S); i > 0; i-- {
if i%2 != 0 {
continue
}
for j := 0; j <= len(S)-i; j++ {
substring := S[j : i+j]
if isStringCharactersEven(substring) {
return len(substring)
}
}
}
return 0
}
func isStringCharactersEven(s string) bool {
var r ByRune = []rune(s)
sort.Sort(r)
prev := 0
for i := 0; i < len(r); i++ {
if i%2 == 1 {
if int(r[i]) != prev {
return false
}
} else {
prev = int(r[i])
}
}
return true
}
// ByRune is Type of rune array
type ByRune []rune
func (r ByRune) Len() int { return len(r) }
func (r ByRune) Swap(i, j int) { r[i], r[j] = r[j], r[i] }
func (r ByRune) Less(i, j int) bool { return r[i] < r[j] }
Analysis
Code: 15:41:48 UTC,
go,
final,
score:
50
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
import (
"sort"
)
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) int {
// write your code in Go 1.4
for i := len(S); i > 0; i-- {
if i%2 != 0 {
continue
}
for j := 0; j <= len(S)-i; j++ {
substring := S[j : i+j]
if isStringCharactersEven(substring) {
return len(substring)
}
}
}
return 0
}
func isStringCharactersEven(s string) bool {
var r ByRune = []rune(s)
sort.Sort(r)
prev := 0
for i := 0; i < len(r); i++ {
if i%2 == 1 {
if int(r[i]) != prev {
return false
}
} else {
prev = int(r[i])
}
}
return true
}
// ByRune is Type of rune array
type ByRune []rune
func (r ByRune) Len() int { return len(r) }
func (r ByRune) Swap(i, j int) { r[i], r[j] = r[j], r[i] }
func (r ByRune) Less(i, j int) bool { return r[i] < r[j] }Analysis summary
The following issues have been detected: timeout errors.
Analysis
Detected time complexity:
O(N**3)
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
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
Correctness/performance tests
1.
0.001 s
OK
2.
0.012 s
OK
1.
0.024 s
OK
2.
0.016 s
OK
3.
0.001 s
OK
expand all
Performance tests
random2
random strings, all characters, N <= 500
random strings, all characters, N <= 500
✘
TIMEOUT ERROR
running time: 1.36 sec., time limit: 0.10 sec.
running time: 1.36 sec., time limit: 0.10 sec.
1.
1.356 s
TIMEOUT ERROR,
running time: 1.36 sec., time limit: 0.10 sec.
2.
0.780 s
TIMEOUT ERROR,
running time: 0.78 sec., time limit: 0.10 sec.
long_blocks
long blocks of same letters, N <= 100,000
long blocks of same letters, N <= 100,000
✘
TIMEOUT ERROR
running time: >6.00 sec., time limit: 0.10 sec.
running time: >6.00 sec., time limit: 0.10 sec.
1.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.10 sec.
2.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.11 sec.
most_characters
most characters in substring, N <= 100,000
most characters in substring, N <= 100,000
✘
TIMEOUT ERROR
running time: >6.00 sec., time limit: 0.13 sec.
running time: >6.00 sec., time limit: 0.13 sec.
1.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.13 sec.
2.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.13 sec.
3.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.11 sec.
random3
random strings, all characters, N <= 100,000
random strings, all characters, N <= 100,000
✘
TIMEOUT ERROR
running time: >6.00 sec., time limit: 0.14 sec.
running time: >6.00 sec., time limit: 0.14 sec.
1.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.14 sec.
2.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.14 sec.