teddy online judge

17. Collar Roto

Limite de tiempo : 1 seg.   Total runs : 123  Aceptados : 34

Usted tiene un collar de N cuentas (3 <= N <= 350), algunas rojas, otras azules y otras blancas organizadas aleatoriamente. Aquí hay dos ejemplos para n=29:

                1 2                               1 2
            r b b r                           b r r b
          r         b                       b         b
         r           r                     b           r
        r             r                   w             r
       b               r                 w               w
      b                 b               r                 r
      b                 b               b                 b
      b                 b               r                 b
       r               r                 b               r
        b             r                   r             r
         b           r                     r           r
           r       r                         r       b
             r b r                             r r w
            Figura A                         Figura B
                        r cuenta roja
                        b cuenta azul
                        w cuenta blanca

Las cuentas consideradas primera y segunda en el texto que sigue ha sido marcadas en la figura.

La configuración en la Figura A puede ser representada como una cadena de b's y r's, donde b representa una cuenta azul y r representa una roja, de la siguiente manera brbrrrbbbrrrrrbrrbbrbbbbrrrrb .

Suponga que usted tiene que romper el collar en algún punto, ponerlo derecho y luego recolectar las cuentas del mismo color de un extremo hasta que usted llegue a una cuenta de un color diferente, y hacer lo mismo desd el otro extremo (el cual podría o no ser del mismo color que las cuentas recogidas previamente).

Determine el punto donde el collar debería ser roto de tal manera que se recolecte el máximo número de cuentas.

EJEMPLO

Por ejemplo, para el collar de la Figura A, se pueden recolectar 8 cuentas, con el punto de corte o entre la cuenta 9 y la cuenta 10 o entre la cuenta 24 y la cuenta 25.

En algunos collares, se han incluido cuentas blancas como se muestra en la Figura B previamente mostrada. Cuando se recolectan cuentas, una cuenta blanca que se encuentra puede ser tratada como roja o azul y luego pintada del color deseado. La cadena que representa esta configuración incluirá los tres símbolos r, b y w.

Escriba un rograma que determine el mayor número de cuentas que puede ser recolectado de un collar dado.

ENTRADA

Una linea con un entero C. Le siguen C pares de lineas que contienen : N, el número de cuentas y una cadena de N carácteres, cada uno de los cuales es r, b, o w

SALIDA

Una sola línea conteniendo el máximo número de cuentas que pueden ser recolectadas del collar suministrado.

ENTRADA EJEMPLO (archivo data.in)

1
29
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb

SALIDA EJEMPLO (archivo data.out)

11

EXPLICACION DE LA SALIDA

Considere dos copias de las cuentas (como si se dieran la vuelta en los extremos). La cadena de 11 cuentas está marcada.

wwwbbrwrbrbrrbrbrwrwwrbwrwrrb wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
                       ****** *****