Dadas dos strings X e Y, imprima la string más corta que tenga tanto X como Y como subsecuencias. Si existen varias supersecuencias más cortas, imprima cualquiera de ellas. Ejemplos: Input: X = «AGGTAB», Y = «GXTXAYB» Output: «AGXGTXAYB» OR «AGGXTXAYB» OR Any string that represents shortest supersequence of X and Y Input: X = … Continue reading «Impresión de supersecuencia común más corta»
Dadas dos arrays firstArr[] , que consisten solo en elementos distintos, y secondArr[] , la tarea es encontrar la longitud de LCS entre estas 2 arrays. Ejemplos: Entrada: firstArr[] = {3, 5, 1, 8}, secondArr[] = {3, 3, 5, 3, 8} Salida: 3. Explicación: LCS entre estas dos arrays es {3, 5, 8} . Entrada … Continue reading «Subsecuencia común más larga de dos arrays, de las cuales una array consta solo de elementos distintos»
Dadas dos strings A y B , imprima el número mínimo de rebanadas requeridas en A para obtener otra string B. En caso de que no sea posible obtener B de A , imprima «-1». Ejemplos: Entrada: A = “geeksforgeeks”, B = “ksgek” Salida: 5 Explicación: g | ee | k | fragua | … Continue reading «Minimice las particiones en una string dada para obtener otra string»
Dadas dos strings str1 y str2, la tarea es encontrar la longitud de la string más corta que tiene tanto str1 como str2 como subsecuencias. Ejemplos: Input: str1 = «geek», str2 = «eke» Output: 5 Explanation: String «geeke» has both string «geek» and «eke» as subsequences. Input: str1 = «AGGTAB», str2 = «GXTXAYB» Output: 9 … Continue reading «Supersecuencia común más corta»
Dadas dos strings X e Y de longitud m y n respectivamente. El problema es encontrar la longitud de la subsecuencia común más larga de las strings X e Y que contiene todos los caracteres vocálicos. Ejemplos: Input : X = «aieef» Y = «klaief» Output : aie Input : X = «geeksforgeeks» Y = … Continue reading «Longitud de la subsecuencia común más larga que contiene vocales»
Dadas K permutaciones de números de 1 a N en una array 2D arr[][] . La tarea es encontrar la subsecuencia común más larga de estas K permutaciones. Ejemplos: Entrada: N = 4, K = 3 arr[][] = {{1, 4, 2, 3}, {4, 1, 2, 3}, … Continue reading «Encuentre la subsecuencia común más larga (LCS) en K permutaciones dadas»
La mayoría de los problemas de Programación Dinámica se resuelven de dos formas: Tabulación: de abajo hacia arriba Memoización: de arriba hacia abajo Uno de los enfoques más fáciles para resolver la mayoría de los problemas en DP es escribir el código recursivo al principio y luego escribir el método de tabulación de abajo hacia … Continue reading «Memoización (1D, 2D y 3D)»
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 – Part 1»
Dadas dos strings s1 y s2, la tarea es encontrar la longitud de la subsecuencia común más larga presente en ambas. Ejemplos: Entrada: s1 = “ABCDGH”, s2 = “AEDFHR” Salida: 3 LCS para las Secuencias de entrada “AGGTAB” y “GXTXAYB” es “GTAB” de longitud 4. Entrada: s1 = “striver”, s2 = “raj” Salida: 1 La … Continue reading «Subsecuencia común más larga | DP usando Memoización»
Dadas dos strings binarias s1 y s2 . La tarea es elegir una substring de s1 y s2 , digamos sub1 y sub2 de igual longitud, de modo que maximice la función: diversión(s1, s2) = len(sub1) / (2 xor(sub1, sub2) ) Ejemplos: Entrada: s1= “1101”, s2= “1110” Salida: 3 Explicación: A continuación se encuentran las … Continue reading «Maximice la función dada seleccionando substrings de igual longitud de strings binarias dadas»