recursion - problems - Reducción de cadenas-Concurso de programación. Solución necesaria

dynamic programming problems

Question

Tengo una pregunta que nos pide que reduzcamos la cadena de la siguiente manera.

La entrada es una cadena que tiene solo A , B o C La salida debe ser la longitud de la cadena reducida

La cadena puede ser reducida por las siguientes reglas

Si hay 2 letras diferentes adyacentes, estas dos letras pueden reemplazarse por la tercera letra.

Ej. ABA -> CA -> B Entonces la respuesta final es 1 (longitud de la cadena reducida)

Ej. ABCCCCCCC

Esto no se convierte en CCCCCCCC , ya que puede reducirse alternativamente

ABCCCCCCC -> AACCCCCC -> ABCCCCC -> AACCCC -> ABCCC -> AACC -> ABC -> AA

como aquí la longitud es 2 <(longitud de CCCCCCCC )

¿Cómo abordas este problema?

¡Muchas gracias!

Para aclarar las cosas: la pregunta indica que quiere la longitud mínima de la cadena reducida. Entonces en el segundo ejemplo anterior hay 2 soluciones posibles, una CCCCCCCC y la otra AA . Entonces, 2 es la respuesta, ya que la longitud de AA es 2, que es menor que la longitud de CCCCCCCC = 8.

Answer 1

¿No sería un buen comienzo contar qué letra tiene más y buscar formas de eliminarla? Sigue haciendo esto hasta que solo tengamos una letra. Podríamos tenerlo muchas veces, pero mientras sea igual no nos importa, hemos terminado.

Para evitar que algo como ABCCCCCCC se convierta en CCCCCCCC.

Eliminamos la letra más popular:

-ABCCCCCCC
-AACCCCCC
-ABCCCCC
-AACCCC
-ABCCC
-AACC
-A B C
-AUTOMÓVIL CLUB BRITÁNICO

No estoy de acuerdo con el afiche anterior que dice que debemos tener una longitud de 1 o 2, ¿qué sucede si ingreso la cadena de inicio AAA?

Answer 2

Compare dos caracteres a la vez y reemplácelos si los dos caracteres adyacentes no son iguales. Para obtener una solución óptima, ejecute una vez desde el inicio de la cadena y una vez desde el final de la cadena. Devuelve el valor mínimo.

La solución de Rav es:

int same(char* s){
    int i=0;
    for(i=0;i<strlen(s)-1;i++){
            if(*(s+i) == *(s+i+1))
                    continue;
            else
                    return 0;
    }
    return 1;
}


int reduceb(char* s){
    int ret = 0,a_sum=0,i=0;
    int len = strlen(s);
    while(1){
            i=len-1;
            while(i>0){
                    if ((*(s+i)) == (*(s+i-1))){
                                    i--;
                                    continue;
                    } else {
                            a_sum = (*(s+i)) + (*(s+i-1));
                            *(s+i-1) = SUM - a_sum;
                            *(s+i) = ''/0'';
                            len--;
                    }
                    i--;
            }
            if(same(s) == 1){
                    return strlen(s);
                    }
}
}


int reducef(char* s){
    int ret = 0,a_sum=0,i=0;
    int len = strlen(s);
    while(1){
            i=0;
            while(i<len-1){
                    if ((*(s+i)) == (*(s+i+1))){
                                    i++;               
                                    continue;
                    } else {
                            a_sum = (*(s+i)) + (*(s+i+1));
                            *(s+i) = SUM - a_sum;
                            int j=i+1;
                            for(j=i+1;j<len;j++)
                                    *(s+j) = *(s+j+1);
                            len--;
                    }
                    i++;
            }
            if(same(s) == 1){
                    return strlen(s);
                    }
}
}

int main(){
    int n,i=0,f=0,b=0;
    scanf("%d",&n);
    int a[n];

    while(i<n){
            char* str = (char*)malloc(101);
            scanf("%s",str);
            char* strd = strdup(str);
            f = reducef(str);
            b = reduceb(strd);

            if( f > b)
                    a[i] = b;
            else
                    a[i] = f;
            free(str);
            free(strd);
            i++;
    }

    for(i=0;i<n;i++)
            printf("%d/n",a[i]);

}

@Rav

este código fallará para la entrada "abccaccba". la solución debe ser solo "b" pero este código no dará eso. Como no obtengo el lugar correcto para comentar (debido a puntos bajos o cualquier otra razón) lo hice aquí.

Answer 3

Compare dos caracteres a la vez y reemplácelos si los dos caracteres adyacentes no son iguales. Para obtener una solución óptima, ejecute una vez desde el inicio de la cadena y una vez desde el final de la cadena. Devuelve el valor mínimo.

int same(char* s){
    int i=0;
    for(i=0;i<strlen(s)-1;i++){
            if(*(s+i) == *(s+i+1))
                    continue;
            else
                    return 0;
    }
    return 1;
}


int reduceb(char* s){
    int ret = 0,a_sum=0,i=0;
    int len = strlen(s);
    while(1){
            i=len-1;
            while(i>0){
                    if ((*(s+i)) == (*(s+i-1))){
                                    i--;
                                    continue;
                    } else {
                            a_sum = (*(s+i)) + (*(s+i-1));
                            *(s+i-1) = SUM - a_sum;
                            *(s+i) = ''/0'';
                            len--;
                    }
                    i--;
            }
            if(same(s) == 1){
                    return strlen(s);
                    }
}
}


int reducef(char* s){
    int ret = 0,a_sum=0,i=0;
    int len = strlen(s);
    while(1){
            i=0;
            while(i<len-1){
                    if ((*(s+i)) == (*(s+i+1))){
                                    i++;               
                                    continue;
                    } else {
                            a_sum = (*(s+i)) + (*(s+i+1));
                            *(s+i) = SUM - a_sum;
                            int j=i+1;
                            for(j=i+1;j<len;j++)
                                    *(s+j) = *(s+j+1);
                            len--;
                    }
                    i++;
            }
            if(same(s) == 1){
                    return strlen(s);
                    }
}
}

int main(){
    int n,i=0,f=0,b=0;
    scanf("%d",&n);
    int a[n];

    while(i<n){
            char* str = (char*)malloc(101);
            scanf("%s",str);
            char* strd = strdup(str);
            f = reducef(str);
            b = reduceb(strd);

            if( f > b)
                    a[i] = b;
            else
                    a[i] = f;
            free(str);
            free(strd);
            i++;
    }

    for(i=0;i<n;i++)
            printf("%d/n",a[i]);

}

Answer 4

Definamos un autómata con las siguientes reglas (K> = 0):

   Incoming:    A       B       C
Current:    --------------------------
<empty>         A       B       C
A(2K+1)         A(2K+2) AB      AC
A(2K+2)         A(2K+3) AAB     AAC
AB              CA      CB      ABC
AAB             BA      ACB     BC
ABC             CCA     AAB     AAC

y todas las reglas obtenidas por permutaciones de ABC para obtener la definición completa.

Todas las cadenas de entrada que usan una sola letra son irreducibles. Si la cadena de entrada contiene al menos dos letras diferentes, los estados finales como AB o AAB se pueden reducir a una sola letra, y los estados finales como ABC se pueden reducir a dos letras.

En el caso ABC, todavía tenemos que demostrar que la cadena de entrada no se puede reducir a una sola letra por otra secuencia de reducción.

Answer 5

Este es un enfoque codicioso y recorrer el camino comienza con cada par posible y verificar la longitud mínima.

import java.io.*;
import java.util.*;

class StringSim{

public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
    StringTokenizer st = new StringTokenizer(sc.nextLine(), " ");
    int N = Integer.parseInt(st.nextToken());
    String op = "";
    for(int i=0;i<N;i++){
        String str = sc.nextLine();
        op = op + Count(str) + "/n";
    }
    System.out.println(op);
}

public static int Count( String str){
    int min = Integer.MAX_VALUE;
    char pre = str.charAt(0);
    boolean allSame = true;
    //System.out.println("str :" + str);
    if(str.length() == 1){
        return 1;
    }
    int count = 1;
    for(int i=1;i<str.length();i++){
        //System.out.println("pre: -"+ pre +"- char at "+i+" is : -"+ str.charAt(i)+"-");
        if(pre != str.charAt(i)){
            allSame = false;
            char rep = (char)((''a''+''b''+''c'')-(pre+str.charAt(i)));
            //System.out.println("rep :" + rep);
            if(str.length() == 2)
                count = 1;
            else if(i==1)
                count = Count(rep+str.substring(2,str.length()));
            else if(i == str.length()-1) 
                count = Count(str.substring(0,str.length()-2)+rep);
            else
                count = Count(str.substring(0,i-1)+rep+str.substring(i+1,str.length()));

            if(min>count) min=count;
        }else if(allSame){
            count++;
            //System.out.println("count: " + count);
        }
        pre = str.charAt(i);
    }
    //System.out.println("min: " + min);
    if(allSame) return count;
    return min;
  }
}

Answer 6

Este problema puede ser resuelto por un enfoque codicioso. Intenta encontrar la mejor posición para aplicar la transformación hasta que no haya transformación. La mejor posición es la posición con un número máximo de vecinos distintos del personaje transformado.

Answer 7

Hay alguna estructura subyacente que se puede usar para resolver este problema en el tiempo O (n).

Las reglas dadas son (la mayoría de) las reglas que definen un grupo matemático, en particular el grupo D_2 también conocido como K (para el grupo de Klein) o V (alemán para Viergruppe, cuatro grupos). D_2 es ​​un grupo con cuatro elementos, A, B, C y 1 (el elemento de identidad). Una de las realizaciones de D_2 es ​​el conjunto de simetrías de una caja rectangular con tres lados diferentes. A, B y C son rotaciones de 180 grados sobre cada uno de los ejes, y 1 es la rotación de identidad (sin rotación). La tabla de grupos para D_2 es

 |1 A B C
-+------- 
1|1 A B C
A|A 1 C B
B|B C 1 A
C|C B A 1

Como puede ver, las reglas corresponden a las reglas dadas en el problema, excepto que las reglas que involucran a 1 no están presentes en el problema.

Como D_2 es ​​un grupo, cumple una serie de reglas: cierre (el producto de dos elementos del grupo es otro elemento), asociatividad (significado (x*y)*z = x*(y*z) para cualquier elemento x , y , z ; es decir, no importa el orden en que se reducen las cadenas), existencia de identidad (hay un elemento 1 tal que 1*x=x*1=x para cualquier x ), y existencia de inversa (para cualquier elemento x , hay un elemento x^{-1} tal que x*x^{-1}=1 and x^{-1}*x=1 ; en nuestro caso, cada elemento es su propio inverso )

También vale la pena señalar que D_2 es conmutativa , es decir, x*y=y*x para cualquier x,y .

Dada cualquier cadena de elementos en D_2, podemos reducir a un solo elemento en el grupo de una manera codiciosa. Por ejemplo, ABCCCCCCC=CCCCCCCC=CCCCCC=CCCC=CC=1 . Tenga en cuenta que no escribimos el elemento 1 menos que sea el único elemento en la cadena. La asociatividad nos dice que el orden de las operaciones no importa, por ejemplo, podríamos haber trabajado de derecha a izquierda o comenzar en el medio y obtener el mismo resultado. Probemos desde la derecha: ABCCCCCCC=ABCCCCC=ABCCC=ABC=AA=1 .

La situación del problema es diferente porque las operaciones que involucran a 1 no están permitidas, por lo que no podemos simplemente eliminar los pares AA , BB o CC . Sin embargo, la situación no es tan diferente. Considere la cadena ABB . No podemos escribir ABB=A en este caso. Sin embargo, podemos eliminar BB en dos pasos usando A : ABB=CB=A Dado que el orden de operación no importa por asociatividad, tenemos la garantía de obtener el mismo resultado. Entonces no podemos ir directamente de ABB a A pero podemos obtener el mismo resultado por otra ruta.

Dichas rutas alternativas están disponibles siempre que haya al menos dos elementos diferentes en una cadena. En particular, en cada uno de ABB , ACC , BAA , BCC , CAA , CBB , AAB , AAC , BBA , BBC , CCA , CCB , podemos actuar como si tuviéramos la reducción xx=1 y luego soltar el 1 .

Se deduce que cualquier cadena que no sea homogénea (no toda la misma letra) y que tenga una subcadena de doble letra ( AA , BB o CC ) se puede reducir al eliminar la letra doble. Las cadenas que contienen solo dos letras idénticas no se pueden reducir más (porque no hay 1 permitido en el problema), por lo que parece seguro suponer que cualquier cadena no homogénea se puede reducir a A , B , C , AA , BB , CC .

Todavía tenemos que tener cuidado, sin embargo, porque CCAACC podría convertirse en CCCC eliminando el par medio AA , pero eso no es lo mejor que podemos hacer: CCAACC=AACC=CC or AA nos lleva a una cadena de longitud 2.

Otra situación de la que tenemos que tener cuidado es AABBBB . Aquí podríamos eliminar AA para terminar con BBBB , pero es mejor eliminar el medio B primero, luego lo que sea: AABBBB=AABB=AA or BB (ambos son equivalentes a 1 en el grupo, pero no pueden ser más reducido en el problema).

Hay otra situación interesante que podríamos tener: AAAABBBB . La eliminación ciega de pares nos lleva a AAAA o BBBB , pero podríamos hacerlo mejor: AAAABBBB=AAACBBB=AABBBB=AABB=AA or BB .

Lo anterior indica que eliminar ciegamente no es necesariamente la manera de proceder, pero sin embargo fue esclarecedor.

En cambio, parece que la propiedad más importante de una cadena es la no homogeneidad. Si el hilo es homogéneo, deténgase, no hay nada que podamos hacer. De lo contrario, identifique una operación que preserve la propiedad de no homogeneidad si es posible. Afirmo que siempre es posible identificar una operación que preserve la no homogeneidad si la cadena no es homogénea y tiene una longitud de cuatro o más.

Prueba: si una subcadena de 4 contiene dos letras diferentes, se puede introducir una tercera letra en un límite entre dos letras diferentes, por ejemplo, AABA va a ACA . Dado que una u otra de las letras originales debe permanecer sin cambios en algún lugar dentro de la cadena, se deduce que el resultado aún no es homogéneo.

Supongamos que en cambio tenemos una subcadena de 4 que tiene tres elementos diferentes, por ejemplo AABC , con los dos elementos externos diferentes. Luego, si los dos elementos del medio son diferentes, realice la operación en ellos; el resultado es no homogéneo porque los dos elementos más externos todavía son diferentes. Por otro lado, si los dos elementos internos son iguales, por ejemplo, ABBC , entonces tienen que ser diferentes de los dos elementos más externos (de lo contrario, solo tendríamos dos elementos en el conjunto de cuatro, no tres). En ese caso, realice la primera o la tercera operación; eso deja a los últimos dos elementos diferentes (p. ej., ABBC=CBC ) o los dos primeros elementos diferentes (p. ej., ABBC=ABA ), por lo que se preserva la no homogeneidad.

Finalmente, considere el caso donde el primer y el último elemento son iguales. Entonces tenemos una situación como ABCA . Los dos elementos del medio deben ser diferentes de los elementos externos; de lo contrario, tendremos solo dos elementos en este caso, no tres. Podemos tomar la primera operación disponible, ABCA=CCA , y la no homogeneidad se conserva de nuevo.

Fin de la prueba.

Tenemos un algoritmo codicioso para reducir cualquier cadena no homogénea de longitud 4 o superior: elija la primera operación que preserve la no homogeneidad; tal operación debe existir por el argumento anterior.

Ahora hemos reducido al caso en el que tenemos una cadena no homogénea de 3 elementos. Si dos son iguales, tenemos dobles como AAB , etc., que sabemos que se pueden reducir a un solo elemento, o tenemos dos elementos sin doble como ABA=AC=B que también se pueden reducir a un solo elemento, o tenemos tres elementos diferentes como ABC . Hay seis permutaciones, todas las cuales =1 en el grupo por asociatividad y conmutatividad; todos ellos pueden reducirse a dos elementos mediante cualquier operación; sin embargo, no pueden reducirse por debajo de un par homogéneo ( AA , BB o CC ) ya que 1 no está permitido en el problema, por lo que sabemos que es lo mejor que podemos hacer en este caso.

En resumen, si una cadena es homogénea, no hay nada que podamos hacer; si una cadena no es homogénea y =A en el grupo, se puede reducir a A en el problema mediante un algoritmo codicioso que mantiene la no homogeneidad en cada paso; lo mismo si la cadena =B o =C en el grupo; finalmente, si una cuerda no es homogénea y =1 en el grupo, se puede reducir mediante un algoritmo codicioso que mantiene la no homogeneidad el mayor tiempo posible a AA , BB o CC . Esos son los mejores que podemos hacer por las propiedades grupales de la operación.

Programa que resuelve el problema:

Ahora, dado que conocemos los posibles resultados, nuestro programa puede ejecutarse en el tiempo O(n) siguiente manera: si todas las letras en la cadena dada son iguales, no es posible ninguna reducción, de modo que solo da salida a la longitud de la cadena. Si la cadena no es homogénea, y es igual a la identidad en el grupo, envíe el número 2; de lo contrario da salida al número 1.

Para decidir rápidamente si un elemento es igual a la identidad en el grupo, utilizamos la conmutatividad y la asociatividad de la siguiente manera: simplemente cuente el número de A ''s, B '' sy C ''en las variables a , b , c . Reemplace a = a mod 2 , b = b mod 2 , c = c mod 2 porque podemos eliminar los pares AA , BB y CC en el grupo. Si ninguno de los resultados a , b , c es igual a 0, tenemos ABC=1 en el grupo, por lo que el programa debería generar 2 porque no es posible una reducción a la identidad 1 . Si los tres elementos a , b , c resultantes son iguales a 0, nuevamente tenemos la identidad ( A , B y C cancelaron por sí mismos) por lo que deberíamos generar 2. De lo contrario, la cadena no es identidad y deberíamos producir 1.

Answer 8

La forma en que se formula esta pregunta, solo hay tres posibilidades distintas:

1. Si la cadena tiene solo un carácter único, la longitud es la misma que la longitud de la cadena.

2/3. Si la cadena contiene más de un carácter único, la longitud es 1 o 2, siempre (según el diseño de los caracteres).

Editar: Como una forma de prueba de concepto, aquí hay algo de gramática y sus extensiones: debo señalar que aunque esto me parece una prueba razonable del hecho de que la longitud se reducirá a 1 o 2, estoy razonablemente seguro de que determinar qué de estas longitudes resultará que no es tan trivial como pensé originalmente (aún tendrías que volver a recurrir a través de todas las opciones para descubrirlo)

S   :   A|B|C|()
S   :   S^

donde () denota la cadena vacía, y s ^ significa cualquier combinación de los caracteres anteriores [A, B, C, ()].

Gramática extendida:

S_1 :   AS^|others
S_2 :   AAS^|ABS^|ACS^|others
S_3 :   AAAS^|
        AABS^ => ACS^ => BS^|
        AACS^ => ABS^ => CS^|
        ABAS^ => ACS^ => BS^|
        ABBS^ => CBS^ => AS^|
        ABCS^ => CCS^ | AAS^|
        ACAS^ => ABS^ => CS^|
        ACBS^ => AAS^ | BBS^|
        ACCS^ => BCS^ => AS^|

Lo mismo sucederá con las gramáticas extendidas que comienzan con B y C (otras). Los casos interesantes son donde tenemos ACB y ABC (tres caracteres distintos en secuencia), estos casos resultan en gramáticas que parecen conducir a longitudes más largas sin embargo:

CCS^:   CCAS^|CCBS^|CCCS^|
        CBS^ => AS^|
        CAS^ => BS^|
        CCCS^|
AAS^:   AAAS^|AABS^|AACS^|
        ACS^ => BS^|
        ABS^ => CS^|
        AAAS^|
BBS^:   BBAS^|BBBS^|BBCS^|
        BCS^ => AS^|
        BAS^ => CS^|
        BBBS^|

Recursivamente, solo conducen a longitudes más largas cuando la cadena restante contiene solo su valor. Sin embargo, debemos recordar que este caso también puede simplificarse, ya que si llegamos a esta área con decir CCCS ^, entonces en un punto anterior teníamos ABC (o consecuentemente CBA). Si miramos hacia atrás, podríamos haber tomado mejores decisiones:

ABCCS^  =>  AACS^   =>  ABS^    =>  CS^ 
CBACS^  =>  CBBS^   =>  ABS^    =>  CS^

Entonces, en el mejor de los casos al final de la cadena cuando tomamos todas las decisiones correctas, terminamos con una cadena restante de 1 carácter seguido de 1 personaje más (ya que estamos al final). En este momento si el personaje es el mismo, entonces tenemos una longitud de 2, si es diferente, entonces podemos reducir una última vez y terminamos con una longitud de 1.

Answer 9

Puede generalizar el resultado en función del recuento de caracteres individuales de la cadena. El algo es el siguiente,

atraviesa la cuerda y obtiene el número de char individual.

Digamos si

• a = no # de a en una cadena dada
• b = no # de b en una cadena dada
• c = no # de c en una cadena dada

entonces puedes decir eso, el resultado será,

if((a == 0 && b == 0 && c == 0) ||
   (a == 0 && b == 0 && c != 0) ||
   (a == 0 && b != 0 && c == 0) ||
   (a != 0 && b == 0 && c == 0))
{
    result = a+b+c;
}
else if(a != 0 && b != 0 && c != 0)
{
    if((a%2 == 0 && b%2 == 0 && c%2 == 0) ||
       (a%2 == 1 && b%2 == 1 && c%2 == 1))
        result = 2;
    else
        result = 1;
}
else if((a == 0 && b != 0 && c != 0) || 
        (a != 0 && b == 0 && c != 0) || 
        (a != 0 && b != 0 && c == 0))
{
    if(a%2 == 0 && b%2 == 0 && c%2 == 0)
        result = 2;
    else
        result = 1;
}

Answer 10

Puedes resolver esto usando 2 pases.

En el primer pase que aplica

len = strlen (str) ;
index = 0 ;
flag = 0 ;

/* 1st pass */
for ( i = len-1 ; i > 0 ; i -- ) {
  if ( str[i] != str[i-1] ) {
    str[i-1] = getChar (str[i], str[i-1]) ;
    if (i == 1) {
      output1[index++] = str[i-1] ;
      flag = 1 ;
      break ;
    }
  }
  else output1[index++] = str[i] ;

}

if ( flag == 0 ) 
  output1[index++] = str[i] ;
output1[index] = ''/0'';

Y en el segundo pase, aplicará lo mismo en ''output1'' para obtener el resultado. Por lo tanto, uno es pase adelante otro es paso hacia atrás.

Answer 11

Siguiendo las observaciones de NominSim, esta es probablemente una solución óptima que se ejecuta en tiempo lineal con O (1) uso de espacio. Tenga en cuenta que solo es capaz de encontrar la longitud de la reducción más pequeña, no la cadena reducida en sí misma:

def reduce(string):
    a = string.count(''a'')
    b = string.count(''b'')
    c = string.count(''c'')
    if ([a,b,c].count(0) >= 2):
        return a+b+c
    elif (all(v % 2 == 0 for v in [a,b,c]) or all(v % 2 == 1 for v in [a,b,c])):
        return 2
    else:
        return 1

Answer 12

Supongo que está buscando la longitud de la cadena más corta posible que se puede obtener después de la reducción.

Una solución simple sería explorar todas las posibilidades de una manera codiciosa y esperar que no explote exponencialmente. Voy a escribir el pseudocódigo de Python aquí porque es más fácil de comprender (al menos para mí;)):

from collections import deque

def try_reduce(string):
    queue = deque([string])
    min_length = len(string)
    while queue:
        string = queue.popleft()
        if len(string) < min_length:
            min_length = len(string)
        for i in xrange(len(string)-1):
            substring = string[i:(i+2)]
            if substring == "AB" or substring == "BA":
                queue.append(string[:i] + "C" + string[(i+2):])
            elif substring == "BC" or substring == "CB":
                queue.append(string[:i] + "A" + string[(i+2):])
            elif substring == "AC" or substring == "CA":
                queue.append(string[:i] + "B" + string[(i+2):])
    return min_length

Creo que la idea básica es clara: tomas una cola ( std::deque debería estar bien), agregas tu cadena en ella, y luego implementas una primera búsqueda de amplitud simple en el espacio de todas las reducciones posibles. Durante la búsqueda, se toma el primer elemento de la cola, se toman todas las subseries posibles, se ejecutan todas las reducciones posibles y se vuelven a poner las cuerdas reducidas en la cola. Se explora todo el espacio cuando la cola queda vacía.

Answer 13

        int previous = a.charAt(0);
        boolean same = true;
        int c = 0;
        for(int i = 0; i < a.length();++i){
            c ^= a.charAt(i)-''a''+1;
            if(a.charAt(i) != previous) same = false;
        } 
        if(same) return a.length();
        if(c==0) return 2;
        else return 1;

Answer 14

    import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;


public class Sample {

    private static char[] res = {''a'', ''b'', ''c''};
    private char replacementChar(char a, char b) {
        for(char c : res) {
            if(c != a && c != b) {
                return c;
            }
        }
        throw new IllegalStateException("cannot happen. you must''ve mucked up the resource");
    }

    public int processWord(String wordString) {
        if(wordString.length() < 2) {
            return wordString.length();
        }
        String wordStringES = reduceFromEnd(reduceFromStart(wordString));
        if(wordStringES.length() == 1) {
            return 1;
        }
        String wordStringSE = reduceFromStart(reduceFromEnd(wordString));
        if(wordString.length() == 1) {
            return 1;
        }

        int aLen;
        if(isReduced(wordStringSE)) {
            aLen = wordStringSE.length();
        } else {
            aLen = processWord(wordStringSE);
        }
        int bLen;
        if(isReduced(wordStringES)) {
            bLen = wordStringES.length();
        } else {
            bLen = processWord(wordStringES);
        }
        return Math.min(aLen, bLen);
    }

    private boolean isReduced(String wordString) {
        int length = wordString.length();
        if(length < 2) {
            return true;
        }
        for(int i = 1; i < length; ++i) {
            if(wordString.charAt(i) != wordString.charAt(i - 1)) {
                return false;
            }
        }
        return wordString.charAt(0) == wordString.charAt(length - 1);
    }

    private String reduceFromStart(String theWord) {
        if(theWord.length() < 2) {
            return theWord;
        }

        StringBuilder buffer = new StringBuilder();
        char[] word = theWord.toCharArray();
        char curChar = word[0];

        for(int i = 1; i < word.length; ++i) {
            if(word[i] != curChar) {
                curChar = replacementChar(curChar, word[i]);
                if(i + 1 == word.length) {
                    buffer.append(curChar);
                    break;
                }
            } else {
                buffer.append(curChar);
                if(i + 1 == word.length) {
                    buffer.append(curChar);
                }
            }
        }
        return buffer.toString();
    }

    private String reduceFromEnd(String theString) {
        if(theString.length() < 2) {
            return theString;
        }

        StringBuilder buffer = new StringBuilder(theString);
        int length = buffer.length();
        while(length > 1) {
            char a = buffer.charAt(0);
            char b = buffer.charAt(length - 1);
            if(a != b) {
                buffer.deleteCharAt(length - 1);
                buffer.deleteCharAt(0);
                buffer.append(replacementChar(a, b));
                length -= 1;
            } else {
                break;
            }
        }
        return buffer.toString();
    }

    public void go() {
        Scanner scanner = new Scanner(System.in);
        int numEntries = Integer.parseInt(scanner.nextLine());
        List<Integer> counts = new LinkedList<Integer>(); 
        for(int i = 0; i < numEntries; ++i) {
            counts.add((processWord(scanner.nextLine())));
        }
        for(Integer count : counts) {
            System.out.println(count);
        }
    }

    public static void main(String[] args) {
        Sample solution = new Sample();
        solution.go();
    }
}

Answer 15

//C# Coding

using System;

using System.Collections.Generic;


namespace ConsoleApplication1
{

class Program
    {

static void Main(string[] args)

{

/*
         Keep all the rules in Dictionary object ''rules''; 
         key - find string, value - replace with value 
         eg: find "AB" , replace with "AA" 
        */

        Dictionary<string, string> rules = new Dictionary<string, string>();
        rules.Add("AB", "AA");
        rules.Add("BA", "AA");
        rules.Add("CB", "CC");
        rules.Add("BC", "CC");
        rules.Add("AA", "A");
        rules.Add("CC", "C");

        // example string
        string str = "AABBCCCA";

        //output
        Console.WriteLine(fnRecurence(rules, str));
        Console.Read();
    }

    //funcation for applying all the rules to the input string value recursivily
    static string fnRecurence(Dictionary<string, string> rules,string str)
    {
        foreach (var rule in rules)
        {
            if (str.LastIndexOf(rule.Key) >= 0)
            {
                str = str.Replace(rule.Key, rule.Value);
            }
        }

        if(str.Length >1)
        {
            int find = 0;
            foreach (var rule in rules)
            {
                if (str.LastIndexOf(rule.Key) >= 0)
                {
                    find = 1;
                }
            }

            if(find == 1)
            {
                str = fnRecurence(rules, str);
            }
            else
            {
                //if not find any exit 
                find = 0;
                str = str;
                return str;
            }
        }

        return str;

    }


}

}

Answer 16

import java.io.*;
import java.util.*;

class StringSim{

    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        StringTokenizer st = new StringTokenizer(sc.nextLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        String op = "";
        for(int i=0;i<N;i++){
            String str = sc.nextLine();
            op = op + Count(str) + "/n";
        }
        System.out.println(op);
    }

    public static int Count( String str){
        int min = Integer.MAX_VALUE;
        char pre = str.charAt(0);
        boolean allSame = true;
        //System.out.println("str :" + str);
        if(str.length() == 1){
            return 1;
        }
        int count = 1;
        for(int i=1;i<str.length();i++){
            //System.out.println("pre: -"+ pre +"- char at "+i+" is : -"+ str.charAt(i)+"-");
            if(pre != str.charAt(i)){
                allSame = false;
                char rep = (char)((''a''+''b''+''c'')-(pre+str.charAt(i)));
                //System.out.println("rep :" + rep);
                if(str.length() == 2)
                    count = 1;
                else if(i==1)
                    count = Count(rep+str.substring(2,str.length()));
                else if(i == str.length()-1) 
                    count = Count(str.substring(0,str.length()-2)+rep);
                else
                    count = Count(str.substring(0,i-1)+rep+str.substring(i+1,str.length()));

                if(min>count) min=count;
            }else if(allSame){
                count++;
                //System.out.println("count: " + count);
            }
            pre = str.charAt(i);
        }
        //System.out.println("min: " + min);
        if(allSame) return count;
        return min;
    }

}

Answer 17

import java.util.Scanner;

public class StringReduction {

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String str = sc.nextLine();
    int length = str.length(); 
    String result = stringReduction(str);
    System.out.println(result); 
}

private static String stringReduction(String str) {
    String result = str.substring(0);
    if(str.length()<2){
        return str;
    }
    if(str.length() == 2){
        return combine(str.charAt(0),str.charAt(1));
    }
    for(int i =1;i<str.length();i++){
        if(str.charAt(i-1) != str.charAt(i)){ 
            String temp = str.substring(0, i-1) + combine(str.charAt(i-1),str.charAt(i)) + str.substring(i+1, str.length()); 
            String sub = stringReduction(temp);
            if(sub.length() < result.length()){
                result = sub;
            }
        }
    }
    return result;
}

private static String combine(char c1, char c2) { 
    if(c1 == c2){
        return "" + c1 + c2;
    }
    else{
        if(c1 == ''a''){
            if(c2 == ''b''){
                return "" + ''c'';
            }
            if(c2 == ''c'') {
                return "" + ''b'';
            }
        }
        if(c1 == ''b''){
            if(c2 == ''a''){
                return "" + ''c'';
            }
            if(c2 == ''c'') {
                return "" + ''a'';
            }
        }
        if(c1 == ''c''){
            if(c2 == ''a''){
                return "" + ''b'';
            }
            if(c2 == ''b'') {
                return "" + ''a'';
            }
        }
        return null;
    } 
}

}