In this challenge, you will be given a string. You must remove characters until the string is made up of any two alternating characters. When you choose a character to remove, all instances of that character must be removed. Your goal is to create the longest string possible that contains just two alternating letters.
As an example, consider the string "abaacdabd"
. If you delete the character
'a'
, you will be left with the string "bcdbd"
. Now, removing the character
'c'
leaves you with a valid string "bdbd"
having a length of 4. Removing
either 'b'
or 'd'
at any point would not result in a valid string.
Given a string s
, convert it to the longest possible string t
made up only
of altrenating characters. Print the length of string t
on a new line. If no
string t
can be formed, print 0
instead.
Input Format
A single integer, max
.
Constraints:
- 1 <= |
max
| <= 62
Output Format
Print a single integer denoting the maximum length of t
for the given s
; if
it is not possible to form string t
, print 0
instead.
Sample
output00.txt
stretch tree of depth 11 check: 4095
1024 trees of depth 4 check: 31744
256 trees of depth 6 check: 32512
64 trees of depth 8 check: 32704
16 trees of depth 10 check: 32752
long lived tree of depth 10 check: 2047
Solution
main.go
package main
import (
"fmt"
"os"
"runtime"
"runtime/pprof"
"sync"
)
func main() {
if cpup := os.Getenv("CPUPROFILE"); cpup != "" {
f, err := os.Create(cpup)
if err != nil {
fmt.Fprintf(os.Stderr, "Can't create CPU profile file: %v", err)
os.Exit(1)
}
defer f.Close()
if err := pprof.StartCPUProfile(f); err != nil {
fmt.Fprintf(os.Stderr, "Can't profile CPU usage: %v", err)
os.Exit(1)
}
defer pprof.StopCPUProfile()
}
min := 4
var max int
fmt.Scan(&max)
if max < min+2 {
max = min + 2
}
{
st := NewTree(max + 1)
fmt.Printf("stretch tree of depth %d\t check: %d\n", max+1, st.Check())
}
llt := NewTree(max)
var wg sync.WaitGroup
msgs := make([]string, max+1)
for cd := min; cd <= max; cd += 2 {
wg.Add(1)
go func(cd int) {
defer wg.Done()
pool := NewPool(cd)
n := 1 << (max - cd + min)
i := 0
sum := 0
for ; i < n; i++ {
t := NewTreeWithPool(cd, pool)
sum += t.Check()
}
msgs[cd] = fmt.Sprintf("%d\t trees of depth %d\t check: %d", i, cd, sum)
}(cd)
}
wg.Wait()
for cd := min; cd <= max; cd += 2 {
fmt.Println(msgs[cd])
}
fmt.Printf("long lived tree of depth %d\t check: %d\n", max, llt.Check())
if memp := os.Getenv("MEMPROFILE"); memp != "" {
f, err := os.Create(memp)
if err != nil {
fmt.Fprintf(os.Stderr, "Can't create memory profile file: %v", err)
os.Exit(1)
}
defer f.Close()
runtime.GC()
if err := pprof.WriteHeapProfile(f); err != nil {
fmt.Fprintf(os.Stderr, "Can't profile memory usage: %v", err)
os.Exit(1)
}
}
}
type Tree struct {
left, right *Tree
}
func NewTree(d int) Tree {
return NewTreeWithPool(d, NewPool(d))
}
func NewTreeWithPool(d int, pool []Tree) Tree {
if d < 1 {
return Tree{}
}
base := 1 << d
total := base<<1 - 2
pool = pool[:0]
for i := 0; i < base; i++ {
pool = append(pool, Tree{})
}
for i := 0; i < total-2; i += 2 {
pool = append(pool, Tree{&pool[i], &pool[i+1]})
}
return Tree{&pool[total-2], &pool[total-1]}
}
func (t *Tree) Check() int {
if t.left != nil {
return t.left.Check() + t.right.Check() + 1
}
return 1
}
func NewPool(d int) []Tree {
total := 1<<(d+1) - 2
return make([]Tree, total)
}
Privacy policy
This site uses tracking cookies when:
- Comments are loaded. If you don’t want them, just don’t click «Show comments».
If you use only Open Source products, sorry about using tracking cookies, I will replace Disqus as my comments platform in the future.
If you use private source products, worrying about privacy and using this products is like worrying about global warming and not recycling.. So just don’t.. 😒