Permutation in String

Q: ¿Cuál es la complejidad temporal de Permutation in String?

Con una ventana deslizante, es O(m + n) , donde m es la longitud de s1 y n la longitud de s2 . Cuentas s1 una vez y después cada letra de s2 entra en la ventana una vez y sale de ella una vez. Volver a contar cada ventana desde cero cuesta O(n · m) en cambio.

Q: ¿Es «Permutación en una cadena» lo mismo que encontrar un anagrama dentro de una cadena?

Sí. Una permutación de s1 es un anagrama de esta, así que la pregunta es si alguna subcadena de s2 de longitud m es un anagrama de s1 . La comprobación de anagramas entre dos cadenas completas compara los recuentos de letras una vez; aquí, la misma comparación se realiza en una ventana que se desliza a lo largo de s2 .

Q: ¿Por qué la ventana deslizante tiene aquí un tamaño fijo?

Cada permutación de s1 tiene exactamente m letras, así que solo las ventanas de longitud m pueden coincidir. Problemas como el de la subcadena más larga sin repeticiones amplían y reducen la ventana; aquí ambos extremos se mueven juntos, un paso a la vez.

MedioVentana deslizante Hashing

+10

Una permutación de una cadena usa las mismas letras en cualquier orden, cada una tantas veces como en la cadena original: tar, rat y art son permutaciones entre sí. Recibes dos cadenas s1 y s2 formadas por letras minúsculas del alfabeto inglés. Devuelve true si alguna permutación de s1 aparece en s2 como subcadena (una secuencia de caracteres consecutivos), y false en caso contrario.

Función

checkInclusion(s1: string, s2: string) → boolean

s1string: las letras que hay que reordenar
s2string: la cadena en la que buscar
Devuelveboolean: verdadero si una subcadena de s2 es una reordenación de s1

Restricciones

1 ≤ s1.length ≤ 2 × 10⁴
1 ≤ s2.length ≤ 5 × 10⁴
s1 y s2 contienen solo letras inglesas minúsculas (a a z).
s1 puede ser más largo que s2.

Ejemplos

Entrada: s1 = "tar"s2 = "smartphone"
Salida: true
Explicación: La subcadena art en los índices del 2 al 4 de smartphone contiene una a, una r y una t, las mismas letras que tar.

Entrada: s1 = "noon"s2 = "onion"
Salida: false
Explicación: Las subcadenas de longitud 4 son onio y nion. noon necesita dos n y dos o, y cada ventana tiene una i en lugar de una de ellas. Todas las letras de noon aparecen en onion, pero ninguna ventana tiene las cantidades correctas.

Entrada: s1 = "abcd"s2 = "dcb"
Salida: false
Explicación: Cualquier permutación de abcd tiene 4 letras, y dcb solo tiene 3, así que no puede contener una.

+17 pruebas ocultas al enviar

Para ir más allá

¿Puedes devolver todos los índices de s2 donde comienza una permutación de s1, todavía en tiempo O(m + n)?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Enumerar las permutaciones de s1 es inútil: 10 letras ya tienen 3,628,800 ordenaciones. La solución es dejar de preocuparse por el orden. Una subcadena de s2 es una permutación de s1 exactamente cuando tiene la misma longitud m y la misma cantidad de cada letra. Por lo tanto, cada candidata es una ventana de la misma longitud fija, y puedes deslizar una ventana por s2, actualizando sus recuentos de letras con una letra que entra y otra que sale en cada paso.

Cuenta cada ventana desde cero

Correcto, pero no termina con las pruebas más grandes

Intuición

La interpretación literal, generar cada permutación de s1 y buscarla, falla de inmediato: 20 letras tienen más de 2 × 10^18 ordenamientos. En cambio, dale la vuelta a la pregunta. Una subcadena de s2 es una permutación de s1 cuando tiene exactamente m letras y usa cada letra tantas veces como aparece en s1. El orden dentro de ella nunca importa.

Así que cuenta una vez las letras de s1 en una tabla de 26 números, con el índice 0 para a y el 25 para z. Luego toma cada subcadena de s2 de longitud m, cuenta sus letras en una tabla nueva y compara las dos tablas. Para tar en smartphone, las ventanas son sma, mar, art y así sucesivamente, y art coincide: una a, una r, una t.

Esto es correcto porque examina cada candidata. Es lento porque las ventanas contiguas comparten m-1 letras y vuelves a contarlas todas. Con m = 15,000 y n = 50,000, hay 35,001 ventanas de 15,000 letras cada una, unos 5 × 10^8 pasos.

Algoritmo

Si s1 es más larga que s2, devuelve false.
Cuenta las letras de s1 en una tabla need de 26 ceros.
Para cada índice inicial de 0 a n-m, cuenta las letras de los m caracteres a partir de ese inicio en una tabla nueva.
Si esa tabla es igual a need, devuelve true.
Después de la última ventana, devuelve false.

def checkInclusion(s1, s2):
    m, n = len(s1), len(s2)
    if m > n:
        return False
    need = [0] * 26  # need[0] is 'a', need[25] is 'z'
    for ch in s1:
        need[ord(ch) - 97] += 1
    for start in range(n - m + 1):
        # Count the letters of s2[start : start + m] from scratch
        window = [0] * 26
        for i in range(start, start + m):
            window[ord(s2[i]) - 97] += 1
        if window == need:
            return True
    return False

Desliza la ventana y compara 26 recuentos

Intuición

Dos ventanas adyacentes difieren solo en dos letras. Pasar de mar a art elimina la m de la izquierda y añade la t de la derecha. Así que mantén una tabla para la ventana actual y modifícala con un +1 y un -1 en cada paso, en lugar de volver a contar las m letras.

Llena need a partir de s1 y window a partir de las primeras m letras de s2, y compáralas. Después, para cada i desde m hasta n-1, añade s2[i], elimina s2[i-m] y vuelve a comparar. La ventana ahora es s2[i-m+1..i], y sigue teniendo m letras.

Cada paso cuesta dos actualizaciones y una comparación de 26 números, sea cual sea m. En la entrada más grande, eso equivale aproximadamente a 26 × 50,000 = 1.3 × 10^6 operaciones, lineales respecto a la longitud de s2. Esta es la solución que espera la mayoría de los entrevistadores.

Algoritmo

Si s1 es más largo que s2, devuelve false.
Cuenta s1 en need y las primeras m letras de s2 en window.
Si las dos tablas son iguales, devuelve true.
Para cada i desde m hasta n-1: suma 1 para s2[i], resta 1 para s2[i-m] y devuelve true si las tablas son iguales.
Devuelve false.

def checkInclusion(s1, s2):
    m, n = len(s1), len(s2)
    if m > n:
        return False
    need = [0] * 26
    window = [0] * 26
    for i in range(m):
        need[ord(s1[i]) - 97] += 1
        window[ord(s2[i]) - 97] += 1  # the first window is s2[0 : m]
    if window == need:
        return True
    for i in range(m, n):
        window[ord(s2[i]) - 97] += 1      # s2[i] enters on the right
        window[ord(s2[i - m]) - 97] -= 1  # s2[i - m] leaves on the left
        if window == need:
            return True
    return False

Desliza la ventana y sigue las letras desequilibradas

Intuición

Comparar 26 números en cada paso repite trabajo, porque un paso solo cambia dos de ellos. Mantén una tabla balance: balance[c] es la cantidad de copias de la letra c que tiene s1 menos la cantidad que tiene la ventana. La ventana es una permutación de s1 exactamente cuando los 26 balances son 0. Junto a la tabla, mantén unbalanced, la cantidad de letras cuyo balance no es 0, y responde true en cuanto llegue a 0.

El seguimiento tiene una regla. Antes de cambiar balance[c], si vale 0, la letra está a punto de dejar de estar equilibrada, así que suma 1 a unbalanced. Después del cambio, si vale 0, la letra ha alcanzado el equilibrio, así que resta 1. Una letra que entra en la ventana reduce su balance en 1; una letra que sale lo aumenta en 1. Un balance que pasa de 2 a 1 no activa ninguna comprobación, y eso es correcto: la letra estaba desequilibrada y sigue estándolo.

Recorre tar y smartphone. Los balances comienzan así: a: 1, r: 1, t: 1, por lo que unbalanced vale 3. s y m entran y lo aumentan a 5; después, entra a y hace que a llegue a 0: 4. Entra r (3) mientras sale s (2). Entra t (1) mientras sale m (0), y la ventana art es la respuesta.

Puedes comprobar unbalanced == 0 desde la primera letra. Mientras la ventana contenga menos de m letras, los balances suman un número positivo, así que al menos uno no es 0. Cada paso realiza una cantidad fija de trabajo, por lo que el recorrido completo es O(m + n), y la tabla siempre contiene 26 números, lo que requiere un espacio O(1).

Algoritmo

Si s1 es más largo que s2, devuelve false.
Cuenta s1 en balance y establece unbalanced en el número de letras cuyo balance es distinto de 0.
Para cada índice i de s2, resta 1 al balance de s2[i], sumando 1 a unbalanced si ese balance era 0 y restando 1 si pasa a ser 0.
Si i ≥ m, suma 1 al balance de s2[i-m] con el mismo recuento.
Si unbalanced es 0, devuelve true. Después del bucle, devuelve false.

def checkInclusion(s1, s2):
    m, n = len(s1), len(s2)
    if m > n:
        return False
    # balance[c]: copies of letter c in s1 minus copies in the window
    balance = [0] * 26
    for ch in s1:
        balance[ord(ch) - 97] += 1
    unbalanced = sum(1 for b in balance if b != 0)
    for i in range(n):
        # s2[i] enters the window on the right
        c = ord(s2[i]) - 97
        if balance[c] == 0:
            unbalanced += 1
        balance[c] -= 1
        if balance[c] == 0:
            unbalanced -= 1
        # s2[i - m] leaves on the left once the window would pass m letters
        if i >= m:
            c = ord(s2[i - m]) - 97
            if balance[c] == 0:
                unbalanced += 1
            balance[c] += 1
            if balance[c] == 0:
                unbalanced -= 1
        if unbalanced == 0:
            return True
    return False

Errores comunes y casos límite

La mayoría de las respuestas incorrectas se deben a los extremos de la ventana o a comprobar qué letras aparecen en lugar de cuántas veces aparecen.

Comprobar solo que cada letra de s1 esté en la ventana. onio contiene todas las letras de noon, pero no es una permutación de esa palabra. Compara las cantidades.
Eliminar la letra equivocada. Cuando entra s2[i], la letra que sale es s2[i-m], así que la ventana pasa a ser s2[i-m+1..i]. Eliminar s2[i-m+1] deja una ventana de m-1 letras.
Omitir la primera ventana. Si comparas solo después de deslizar la ventana, nunca encontrarás una permutación en el índice 0.
Olvidar el caso en que s1 es más larga que s2. En Rust, n - m con longitudes sin signo produce un desbordamiento, y en Swift el rango 0...(n - m) provoca un error. Devuelve false primero.
Comparar arreglos con == en un lenguaje donde eso compara referencias. En JavaScript y Dart, dos arreglos distintos nunca son ==; en Java, usa Arrays.equals.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de Permutation in String?

Con una ventana deslizante, es O(m + n), donde m es la longitud de s1 y n la longitud de s2. Cuentas s1 una vez y después cada letra de s2 entra en la ventana una vez y sale de ella una vez. Volver a contar cada ventana desde cero cuesta O(n · m) en cambio.

¿Es «Permutación en una cadena» lo mismo que encontrar un anagrama dentro de una cadena?

Sí. Una permutación de s1 es un anagrama de esta, así que la pregunta es si alguna subcadena de s2 de longitud m es un anagrama de s1. La comprobación de anagramas entre dos cadenas completas compara los recuentos de letras una vez; aquí, la misma comparación se realiza en una ventana que se desliza a lo largo de s2.

¿Por qué la ventana deslizante tiene aquí un tamaño fijo?

Cada permutación de s1 tiene exactamente m letras, así que solo las ventanas de longitud m pueden coincidir. Problemas como el de la subcadena más larga sin repeticiones amplían y reducen la ventana; aquí ambos extremos se mueven juntos, un paso a la vez.

¿Puedo usar un mapa hash en lugar de un arreglo de 26 contadores?

Sí, y necesitas uno si las cadenas pueden contener cualquier carácter. Si solo contienen letras minúsculas, un arreglo de 26 elementos es más rápido y usa espacio constante. Con un mapa, elimina una clave cuando su contador baje a 0 para que dos mapas con las mismas letras se consideren iguales, o conserva el contador unbalanced del enfoque anterior, que funciona de la misma manera con un mapa.

Python

def checkInclusion(s1, s2):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

s1 = "tar"
s2 = "smartphone"

Esperado

true

Permutation in String

Función

Restricciones

Ejemplos

Pistas

Solución

Cuenta cada ventana desde cero

Desliza la ventana y compara 26 recuentos

Desliza la ventana y sigue las letras desequilibradas

Errores comunes y casos límite

Preguntas frecuentes4

Problemas similares