Categoría: sliding-window

Longitud de la substring más pequeña que consta de un máximo de caracteres distintos

Posted on by Rudeus Greyrat

Dada una string de longitud N, encuentre la longitud de la substring más pequeña que consta de un máximo de caracteres distintos. Nota: Nuestra salida puede tener el mismo carácter.  Ejemplos:  Input : «AABBBCBB» Output : 5 Input : «AABBBCBBAC» Output : 3 Explanation : Sub-string -> «BAC» Input : «GEEKSGEEKSFOR» Output : 8 Explanation … Continue reading «Longitud de la substring más pequeña que consta de un máximo de caracteres distintos»

Búsqueda de substrings de anagramas (o búsqueda de todas las permutaciones)

Posted on by Rudeus Greyrat

Dado un texto txt[0..n-1] y un patrón pat[0..m-1], escriba una función search(char pat[], char txt[]) que imprima todas las apariciones de pat[] y su permutaciones (o anagramas) en txt[]. Puede suponer que n > m.  La complejidad del tiempo esperado es O(n) Ejemplos:  1) Input: txt[] = «BACDGABCDA» pat[] = «ABCD» Output: Found at Index … Continue reading «Búsqueda de substrings de anagramas (o búsqueda de todas las permutaciones)»

Subarreglo de suma más grande de tamaño K que contiene elementos consecutivos

Posted on by Rudeus Greyrat

Dado un arreglo arr[] que consta de N enteros positivos y un entero positivo K , la tarea es encontrar la suma máxima del subarreglo de tamaño K tal que contenga K elementos consecutivos en cualquier combinación. Ejemplos: Entrada: arr[] = {10, 12, 9, 8, 10, 15, 1, 3, 2}, K = 3 Salida: 27 … Continue reading «Subarreglo de suma más grande de tamaño K que contiene elementos consecutivos»

Subarreglo de suma máxima de tamaño K con suma menor que X

Posted on by Rudeus Greyrat

Dado un arreglo arr[] y dos enteros K y X , la tarea es encontrar la suma máxima entre todos los subarreglos de tamaño K con la suma menor que X . Ejemplos: Entrada: arr[] = {20, 2, 3, 10, 5}, K = 3, X = 20 Salida: 18 Explicación: el subarreglo de tamaño 3 … Continue reading «Subarreglo de suma máxima de tamaño K con suma menor que X»

Subarreglo de suma más grande con al menos k números

Posted on by Rudeus Greyrat

Dado un arreglo, encuentra el subarreglo (que contiene al menos k números) que tiene la suma más grande. Ejemplos:   Input : arr[] = {-4, -2, 1, -3} k = 2 Output : -1 The sub array is {-2, 1} Input : arr[] = {1, 1, 1, 1, 1, 1} k = 2 Output : 6 The … Continue reading «Subarreglo de suma más grande con al menos k números»

Longitud de la substring más pequeña de una string dada que contiene otra string como subsecuencia | conjunto 2

Posted on by Rudeus Greyrat

Dadas dos strings A y B , la tarea es encontrar la substring más pequeña de A que tenga B como subsecuencia . Ejemplos: Entrada: A = «abcdefababaef», B = «abf» Salida: 5 Explicación: la substring más pequeña de A que tiene B como subsecuencia es abcdef. Por lo tanto, la longitud requerida es 5. … Continue reading «Longitud de la substring más pequeña de una string dada que contiene otra string como subsecuencia | conjunto 2»

Comprobar si existe o no un subarreglo de longitud K con suma igual al factorial de un número

Posted on by Rudeus Greyrat

Dado un arreglo arr[] de N enteros y un entero K, la tarea es encontrar un subarreglo de longitud K con una suma de elementos igual al factorial de cualquier número . Si no existe tal subarreglo, imprima » -1″ . Ejemplos: Entrada: arr[] = {23, 45, 2, 4, 6, 9, 3, 32}, K = … Continue reading «Comprobar si existe o no un subarreglo de longitud K con suma igual al factorial de un número»

Cuente los subarreglos con una suma igual a su valor XOR

Posted on by Rudeus Greyrat

Dado un arreglo arr[] que contiene N elementos, la tarea es contar el número de sub-arreglos cuyo XOR de todos los elementos es igual a la suma de todos los elementos en el subarreglo. Ejemplos:   Entrada: arr[] = {2, 5, 4, 6}  Salida: 5  Explicación:  Todos los subarreglos {{2}, {5}, {4}, {6}} satisfacen la condición anterior … Continue reading «Cuente los subarreglos con una suma igual a su valor XOR»

Longitud de la substring más pequeña que se reemplazará para hacer que la frecuencia de cada carácter sea N/3

Posted on by Rudeus Greyrat

Dada una string str de longitud N (divisible por 3) que consta de al menos tres caracteres distintos, la tarea es encontrar la longitud de la substring más pequeña cuyos caracteres se pueden reemplazar para que cada carácter aparezca exactamente N/3 veces. Ejemplos: Entrada: str = “ABB” Salida: 1 Explicación: Una forma óptima es reemplazar … Continue reading «Longitud de la substring más pequeña que se reemplazará para hacer que la frecuencia de cada carácter sea N/3»

Minimice la diferencia de índice (j – i) de modo que el rango [arr[i], arr[j]] contenga al menos K enteros impares

Posted on by Rudeus Greyrat

Dada una array arr[] que tiene N enteros en orden no decreciente y un entero K, la tarea es encontrar el valor mínimo de (j – i) para un par (i, j) tal que el rango [arr[i] , arr[j]] contiene al menos K enteros impares.  Ejemplos : Entrada : arr[] = {1, 3, 6, 8, … Continue reading «Minimice la diferencia de índice (j – i) de modo que el rango [arr[i], arr[j]] contenga al menos K enteros impares»