We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Se le puede dar un enfoque de programacion dinamica mucho para sencillo para resolver el ejercicio que el que esta dado por el editorial
el cual consiste en calcular las combinaciones apartir de subproblemas mas pequeños se explica un poco mejor con un ejemplo.
ABBA que es el ejemplo dado por el ejercicio puede ser resuelto usando el enfoque anteriormente mencionado.
ABBA = a la descomposicion de ABB quitando dos caracteres y concatenandolo al nuevo caractere A + la suma de la descomposocion ABB quitando un
unico caracter.
Es decir ABB = {A,B} (es un caso basico calcular para los casos de 3 letras si ninguna se repite es 3 si dos se repiten 2 y 1 para cuando todas son iguales)y si concatenamos la A quedaria ABBA (cadena original) por lo tanto ya sabemos que {A,B} son parte del resultado si concatenamos cada subcadena con A ya que por defecto si se probaran todas las combinaciones aquellas que terminan en A estarian allÃ, para explicar mejor
ABBA = {AA , BA} esta es sola una parte de la combinacion la cual es la correspondiente a tapar las letras anteriores pero dejar la ultima (A) sin tapar (eliminar) y ya es algo que teniamos anteriormente calculado son exactamente las mismas combinaciones de ABB + A. ahora faltan aquellas combinaciones que vienen dadas por tapar la ultima letra es decir si se elimina el ultimo caracter quedaria la cadena ABB ahora ya quitamos uno de los caracteres por lo tanto solo queda quitar otro y ver que combinaciones se generan sin que se repitan pero para el caso de encontrar que cadenas se repiten y cuales no eliminando una sola letra puede ser descompuesto tambien en problemas mas pequeños por ejemplo AAA = 1 por que AA solo genera una combinacion y si la siguiente letra es igual a la anterior sigue generando la misma cantidad pero si es diferente genera una combinacion mas (aplicar esto para n concatenaciones). Ahora ABB eliminando un solo caracter quedaria = {AB , BB} (no es necesario tener que guardar las cadenas como explicare en un momento) ABBA = {AA , BA} + {AB,BB} = 4 elementos
ahora para eliminar cadenas repetidas de las subcadenas a las cuales se les eliminan dos elementos solo basta revisar que cadena[n] != cadena[n - 1] en ese caso se le suman i - 1 de los elementos que estan en el subconjunto resultante de tapar un elemento de la subcadena esto es debido a que en el subconjunto solo se generaran elementos que terminen en en los dos ultimos caracteres entonces solo basta probar que dichos elementos no estan en el sub conjunto resultante de eliminar dos elementos y esto puede ser comprobado solo con el ultimo caracter (el cual esta en la cadena original).
Ahora falta cadena[n-2] != cadena[n] si eso ocurre se le suma 1 que seria por ejemplo en el caso de ABC donde se generan dos elementos que terminan en C y uno en B {AC,BC , AB} cadena[n-2] corresponde a AB que es la unica diferente.
Aplicar esto para ABBA + String
Apesar de lo engorroso de la explicacion y que es un poco dificil de visualizar resulta facil de programar son unas 10 lineas en lenguaje C y es de O(n).
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Beautiful Strings
You are viewing a single comment's thread. Return to all comments →
Se le puede dar un enfoque de programacion dinamica mucho para sencillo para resolver el ejercicio que el que esta dado por el editorial el cual consiste en calcular las combinaciones apartir de subproblemas mas pequeños se explica un poco mejor con un ejemplo.
ABBA que es el ejemplo dado por el ejercicio puede ser resuelto usando el enfoque anteriormente mencionado. ABBA = a la descomposicion de ABB quitando dos caracteres y concatenandolo al nuevo caractere A + la suma de la descomposocion ABB quitando un unico caracter. Es decir ABB = {A,B} (es un caso basico calcular para los casos de 3 letras si ninguna se repite es 3 si dos se repiten 2 y 1 para cuando todas son iguales)y si concatenamos la A quedaria ABBA (cadena original) por lo tanto ya sabemos que {A,B} son parte del resultado si concatenamos cada subcadena con A ya que por defecto si se probaran todas las combinaciones aquellas que terminan en A estarian allÃ, para explicar mejor ABBA = {AA , BA} esta es sola una parte de la combinacion la cual es la correspondiente a tapar las letras anteriores pero dejar la ultima (A) sin tapar (eliminar) y ya es algo que teniamos anteriormente calculado son exactamente las mismas combinaciones de ABB + A. ahora faltan aquellas combinaciones que vienen dadas por tapar la ultima letra es decir si se elimina el ultimo caracter quedaria la cadena ABB ahora ya quitamos uno de los caracteres por lo tanto solo queda quitar otro y ver que combinaciones se generan sin que se repitan pero para el caso de encontrar que cadenas se repiten y cuales no eliminando una sola letra puede ser descompuesto tambien en problemas mas pequeños por ejemplo AAA = 1 por que AA solo genera una combinacion y si la siguiente letra es igual a la anterior sigue generando la misma cantidad pero si es diferente genera una combinacion mas (aplicar esto para n concatenaciones). Ahora ABB eliminando un solo caracter quedaria = {AB , BB} (no es necesario tener que guardar las cadenas como explicare en un momento) ABBA = {AA , BA} + {AB,BB} = 4 elementos ahora para eliminar cadenas repetidas de las subcadenas a las cuales se les eliminan dos elementos solo basta revisar que cadena[n] != cadena[n - 1] en ese caso se le suman i - 1 de los elementos que estan en el subconjunto resultante de tapar un elemento de la subcadena esto es debido a que en el subconjunto solo se generaran elementos que terminen en en los dos ultimos caracteres entonces solo basta probar que dichos elementos no estan en el sub conjunto resultante de eliminar dos elementos y esto puede ser comprobado solo con el ultimo caracter (el cual esta en la cadena original). Ahora falta cadena[n-2] != cadena[n] si eso ocurre se le suma 1 que seria por ejemplo en el caso de ABC donde se generan dos elementos que terminan en C y uno en B {AC,BC , AB} cadena[n-2] corresponde a AB que es la unica diferente. Aplicar esto para ABBA + String Apesar de lo engorroso de la explicacion y que es un poco dificil de visualizar resulta facil de programar son unas 10 lineas en lenguaje C y es de O(n).