Two Characters

Coding challenges are a great resource for learning coding techniques and improve analytical thinking, this is a collection of challenges from different platforms.

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

10
beabeefeab

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

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
}