Two Characters

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

The first line contains a single integer denoting the length of s.

The second line contains string s.

Constraints:

  • 1 <= |s| <= 1000

  • s only contains lowercase English alphabetic letters ascii[a-z].

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

input00.txt
10
beabeefeab
output00.txt
5

Explanation

The characters present in s are 'a', 'b', 'e', and 'f'. This means that t must consist of two of those characters and we must delete two others. Our choices for characters to leave are [a,b], [a,e], [a, f], [b, e], [b, f] and [e, f].

If we delete 'e' and 'f', the resulting string is "babab". This is a valid t as there are only two distinct characters ('a' and 'b'), and they are alternating within the string.

If we delete 'a' and 'f', the resulting string is "bebeeeb". This is not a valid string t because there are consecutive 'e''s present. Removing them would leave consecutive 'b''s , so this fails to produce a valid string t.

Other cases are solved similarly.

"babab" is the longest string we can create.

Solution

main.go
package main

import "fmt"

func main() {
  var (
    l int
    s string

    tc = NewTC()
  )

  fmt.Scan(&l)
  fmt.Scan(&s)

  for i := 0; i < l; i++ {
    tc.Add(s[i])
  }

  fmt.Println(tc.Longest())
}

type TC struct {
  letters map[byte]int
  pairs   map[string]int
}

func NewTC() *TC {
  return &TC{
    letters: make(map[byte]int),
    pairs:   make(map[string]int),
  }
}

func (tc *TC) Add(c byte) {
  if _, ok := tc.letters[c]; !ok {
    tc.addNew(c)
    return
  }

  tc.letters[c] += 1

  for p, n := range tc.pairs {
    if (p[0] != c && p[1] != c) || n == 0 {
      continue
    }

    n++

    if (p[0] == c && n%2 == 0) || (p[1] == c && n%2 == 1) {
      n = 0
    }

    tc.pairs[p] = n
  }
}

func (tc *TC) Longest() int {
  max := 0

  for _, n := range tc.pairs {
    if n > max {
      max = n
    }
  }

  return max
}

func (tc *TC) addNew(c byte) {
  for l, n := range tc.letters {
    if n != 1 {
      continue
    }

    p := string([]byte{l, c})
    tc.pairs[p] = 2
  }

  tc.letters[c] = 1
}
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 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.. 😒