Dadas dos strings s1, s2 y K, encuentre la longitud de la subsecuencia más larga formada por segmentos consecutivos de al menos longitud K. Ejemplos: Input : s1 = aggayxysdfa s2 = aggajxaaasdfa k = 4 Output : 8 Explanation: aggasdfa is the longest subsequence that can be formed by taking consecutive segments, minimum of … Continue reading «LCS formado por segmentos consecutivos de al menos longitud K»
Dada una array A[] que consta de N enteros distintos y otra array B[] que consta de M enteros, la tarea es encontrar el número mínimo de elementos que se agregarán a la array B[] de modo que la array A[] se convierta en el subsecuencia de la array B[] . Ejemplos: Entrada: N = … Continue reading «Minimice los elementos que se agregarán a una array dada de modo que contenga otra array dada como su subsecuencia | conjunto 2»
Dadas dos strings S y T, encuentre la longitud de la subsecuencia más corta en S que no sea una subsecuencia en T. Si no es posible tal subsecuencia, devuelva -1. Una subsecuencia es una secuencia que aparece en el mismo orden relativo, pero no necesariamente contigua. Una string de longitud n tiene 2^n posibles … Continue reading «Subsecuencia poco común más corta»
Dadas dos strings ‘str1’ y ‘str2’ de tamaño m y n respectivamente. La tarea es eliminar/borrar e insertar el número mínimo de caracteres de/en str1 para transformarlo en str2. Es posible que el mismo carácter deba eliminarse/eliminarse de un punto de str1 e insertarse en otro punto. Ejemplo 1: Input : str1 = «heap», str2 … Continue reading «Número mínimo de eliminaciones e inserciones para transformar una string en otra»
Dadas dos arrays A[] y B[] que consisten en M y N enteros respectivamente, y un entero C , la tarea es encontrar el costo mínimo requerido para hacer que la secuencia A sea exactamente igual a B (consiste solo en elementos distintos) por realizando las siguientes operaciones en la array A[] : Elimina cualquier … Continue reading «Costo mínimo requerido para reorganizar una array dada para que sea igual a otra array dada»
Hemos discutido los subproblemas superpuestos y las propiedades de la subestructura óptima en el conjunto 1 y el conjunto 2, respectivamente. También discutimos un problema de ejemplo en el Conjunto 3 . Analicemos el problema de la subsecuencia común más larga (LCS) como un problema de ejemplo más que se puede resolver mediante la … Continue reading «Subsecuencia común más larga | DP-4»
Dada una string, averigüe si la string es K-Palindrome o no. Una string K-palindrome se transforma en un palindrome al quitarle como máximo k caracteres. Ejemplos: Input : String – abcdecba, k = 1 Output : Yes String can become palindrome by removing 1 character i.e. either d or e Input : String – abcdeca, … Continue reading «Encuentra si la string es K-Palindrome o no | conjunto 2»
Dadas dos arrays A[] y B[] , la tarea es encontrar el número máximo de líneas sin cruzar entre los elementos de las dos arrays dadas. Se puede dibujar una línea recta entre dos elementos de array A[i] y B[j] solo si: A[i] = B[j] La línea no se cruza con ninguna otra línea. Ejemplos: … Continue reading «Número máximo de líneas no cruzadas entre dos arrays dadas»
Se le dan dos strings. ¿Ahora tiene que imprimir todas las subsecuencias comunes más largas en orden lexicográfico? Ejemplos: Input : str1 = «abcabcaa», str2 = «acbacba» Output: ababa abaca abcba acaba acaca acbaa acbca Este problema es una extensión de la subsecuencia común más larga . Primero encontramos la longitud de LCS y almacenamos … Continue reading «Imprime todas las subsecuencias comunes más largas en orden lexicográfico»
Dadas dos strings A y B . La tarea es contar el número de formas de insertar un carácter en la string A para aumentar la longitud de la subsecuencia común más larga entre la string A y la string B en 1. Ejemplos: Entrada: A = “aa”, B = “baaa” Salida: 4 La subsecuencia … Continue reading «Número de formas de insertar un carácter para aumentar el LCS en uno»