[Leetcode] 0076. Subcadena de ventana mínima

Explore diversas soluciones LeetCode en Python, C++, JavaScript, SQL y TypeScript. Ideal para preparación de entrevistas, aprendizaje y práctica de código en múltiples lenguajes de programación. Enlace de repositorio de Github

Tabla de contenido

Duro

Dadas dos cuerdas s y a de longitudes metro y norte respectivamente, volver el ventana mínima subcadena de s de tal manera que cada carácter en a (incluidos duplicados) está incluido en la ventanaSi no existe dicha subcadena, devuelve la cadena vacía "".

Los casos de prueba se generarán de manera que la respuesta sea único.

Ejemplo 1:

Aporte: s = "ADOBECODEBANC", t = "ABC"
Producción: "BANCO"
Explicación: La subcadena de ventana mínima "BANC" incluye 'A', 'B' y 'C' de la cadena t.

Ejemplo 2:

Aporte: s = "un", t = "un"
Producción: "a"
Explicación: La cadena completa s es la ventana mínima.

Ejemplo 3:

Aporte: s = "a", t = "aa"
Producción: ""
Explicación: Ambos "a" de t deben estar incluidos en la ventana. Dado que la ventana más grande de s solo tiene un "a", devuelve una cadena vacía.

Restricciones:

m == s.longitud
n == t.longitud
1 <= m, n <= 10 ⁵
s y a Consta de letras inglesas mayúsculas y minúsculas.

Hacer un seguimiento: ¿Podrías encontrar un algoritmo que se ejecute en O(metro + norte) ¿tiempo?

Pitón

				
					Complejidad de tiempo #: O(len(s) + len(t)) Complejidad de espacio #: O(len(s) + len(t)) de colecciones importar Counter, defaultdict clase Solución: def minWindow(self, s: str, t: str) -> str: reqCount = defaultdict(int) ventana = defaultdict(int) resultado = [-1, -1] resultLen = float('inf') actual = 0 para char en t: reqCount[char] + = 1 requerido = len(reqCount) izquierda = 0 para derecha en rango(len(s)): char = s[derecha] si char en reqCount: ventana[char] += 1 si ventana[char] == reqCount[char ]: actual += 1 mientras actual == requerido: si (derecha - izquierda + 1) < resultadoLen: resultadoLen = derecha - izquierda + 1 resultado = [izquierda, derecha] leftChar = s[izquierda] si leftChar en ventana: ventana[ leftChar] -= 1 si ventana[leftChar] < reqCount[leftChar]: actual -= 1 izquierda += 1 devolver s[result[0]:result[1] + 1] si resultLen != float('inf') de lo contrario "" S = "ADOBECODEBANC" T = "ABC" imprimir(Solución().minWindow(S, T))

Duro

Pitón

Artículos relacionados