Técnicas para Algoritmos: Sliding Windows #2

Dada una cadena(st) y un patrón(pt), averigüe si la cadena contiene alguna permutación del patrón.

Detalles: 

Si una cadena tiene 'n' caracteres distintos, tendrá n! Permutaciones. Del ejemplo anterior podemos decir que una cadena de 3 caracteres tiene un total de  3! = 3 *2*1 = 6 permutaciones.

La permutación se define como la reorganización de los caracteres de la cadena. Por ejemplo, "abc" tiene las siguientes seis permutaciones:

1. abc

2. acb

3. bac

4. bca

5. cab

6. cba

Escenarios de prueba: 

Escenario #1: 

Entrada: st="oidbcaf", pt="abc" (Strings).

Salida:  true (Boolean).

Explicación: La cadena contiene "bca", que es una permutación del patrón dado.

Escenario #2: 

Entrada: st="odicf", pt="dc" (Strings).

Salida:  false (Boolean).

Explicación: No hay permutación del patrón presente en la cadena dada como una subcadena..

Escenario #3: 

Entrada: st="bcdxabcdy", pt="bcdyabcdx" (Strings).

Salida:  true (Boolean).

Explicación:Tanto la cadena como el patrón son una permutación el uno del otro.

Escenario #4: 

Entrada: st="aaac", pt="abc" (Strings).

Salida:  false (Boolean).

Explicación:No posee el st los caracteres necesarios para ser una permutación de pt.

Estrategia de solución:

Para definir si alguna permutación del patrón (pt) se encuentra dentro del string (st), solo es necesario  encontrar cada carácter del patrón en forma consecutiva en el string como podemos ver en el escenario #1. Para esto contaremos la ocurrencia de los caracteres del pt en el st, y compararemos hasta que el número de coincidencias sea igual al número de caracteres distintos en el pt.

Las imágenes siguiente muestra dos variables y una condición que son vitales para la condición de fin del algoritmo que vamos a establecer, la primera es countMatch que lleva la cuenta de las veces que un carácter del pt aparece en st. La otra variable importante es ptSet como su nombre lo indica es un objeto Set que contiene la cantidad de caracteres distintos dentro del patrón. La propiedad size me dice el tamaño del objeto Set.

Creación del objeto ptSet:

            

Creación del countMatch:

Condición de fin, si esta condición llega a cumplirse quiere decir que permutación existe:

Debemos crear una forma rápida de comprobar si un caráter seleccionado se encuentra dentro del patrón a buscar, para esto crear un Objeto que sirva como tabla hash o diccionario con clave-valor, en donde valor sería la ocurrencia del caráter dentro de patrón.

Creación del objeto frecuenciaCharPt a partir del string pt, esto nos permite tener una tabla hash con cada caráter y su frecuencia:

Creamos la estrategia de solución Sliding Windows con un tamaño variable nunca mayor al número de caracteres en pt, la condición es ir modificando el tamaño de la ventana por todo el string  para buscar los caracteres consecutivos que coincidan con pt.

• Las variables start y end nos permiten llevar el tamaño de nuestra ventana (window) imaginaria, estas dos variables son índices de caracteres en el string st.  Para poder tener comparaciones con los caracteres usamos las variables endChar y startChar.

• El índice end sirve para aumentar el tamaño de nuestra ventana mientras crece su valor empezando en 0 hasta el tamaño máximo st. Por otra parte el índice start reduce el tamaño de la ventana mientras aumenta de valor, solo debe incrementar su valor cuando la window length sea mayor al tamaño de pt.

El  Sliding Window de este problema tiene tres partes principales que son:

Donde llevamos el conteo de los caracteres coincidentes entre el pt y  st. La idea es que cuando el caracter se encuentre dentro del patrón se le reste 1 a la frecuencia del mismo, si esta frecuencia luego de restarle coincide con el valor 0 quiere decir que ha ocurrido un match e incrementamos el valor del contador countMatch.

Lo siguiente es establecer inmediatamente la condición para comprobar si realmente el número de countMatch coincide con el número de caracteres distintos en pt y se deba retornar el valor true, en caso contrario seguimos buscando.

La última parte son las condiciones para incrementar el start de nuestra ventana, si nuestra ventana ya es mayor que el tamaño de nuestro pt es necesario hacer esta operación en donde retiramos un caracter de la venta. Al retirar el caracter debemos observar si su frecuencia ya es cero, en caso de ser cero debemos aumentar su frecuencia en uno y reducir nuestro countMatch en 1 para mantener nuestro conteo coherente mientras trasladamos la ventana.

El ciclo principal del algoritmo debe recorrer el st entero tomando en consideración el ‘Sliding Window’. Si el recorrido de st termina sin que se cumpla la condición de fin donde se encuentra alguna permutación de los caracteres de pt, al final del recorrido se debe retornar el valor false.

Código completo de la solución:

Big Oh del algoritmo:

Se puede notar que es un algoritmo O(m+n), donde tenemos que m es la cantidad de caracteres de st y n la cantidad de caracteres en pt. Posee dos ciclos que no están anidados.  En definitiva la O(n) lo representa para resumir.

Realizar pruebas del algoritmo usando los escenarios:

El objetivo de esta parte es que el estudiante ejecute el algoritmo según los escenarios de pruebas que presentamos al inicio. La depuración del algoritmo paso a paso es vital para entender la estrategia que se utilizó en el mismo.

Código en Github, podrás encontrar otros algoritmos y sus soluciones. Si te sirve de ayuda deja una estrella para el repositorio.