Partition Labels

+10

Recibes una cadena s de letras minúsculas. Divídela en tantas partes consecutivas como puedas, de modo que cada letra aparezca en una sola parte: si una letra aparece en una parte, todas sus copias están en esa parte. Devuelve las longitudes de las partes de izquierda a derecha.

Función

partitionLabels(s: string) → integer-array

sstring: la cadena que se va a cortar, solo letras minúsculas
Devuelveinteger-array: la longitud de cada parte, de izquierda a derecha

Restricciones

1 ≤ s.length ≤ 5 × 10⁴
s contiene solo letras minúsculas del inglés.
Las partes mantienen su orden y, juntas, componen todo s, así que sus longitudes suman s.length.

Ejemplos

Entrada: s = "abacdcefe"
Salida: [3, 3, 3]
Explicación: Las a están en 0 y 2, las c en 3 y 5 y las e en 6 y 8, así que los cortes van después de aba y después de cdc. Ninguna parte se puede volver a cortar, porque cada una empieza y termina con la misma letra.

+14 pruebas ocultas al enviar

Pistas

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

0 de 3 abiertas

Solución

Un corte solo se permite donde no aparece ninguna letra a ambos lados, y la mejor respuesta corta en cada uno de esos lugares. Comprobar cada lugar volviendo a recorrer la cadena requiere tiempo cuadrático. Registra primero la última posición de cada letra y una pasada de izquierda a derecha encuentra todos los cortes, porque una parte tiene que extenderse hasta la última copia de cada letra que contiene.

Prueba cada espacio en blanco

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

Intuición

Hay n-1 espacios entre letras vecinas. Solo se puede hacer un corte en un espacio si no aparece ninguna letra a ambos lados, ya que una letra dividida por el corte quedaría en dos partes. Hacer todos los cortes permitidos produce la mayor cantidad de partes. Considera una pieza entre dos cortes permitidos vecinos: ninguna de sus letras aparece a la izquierda del corte izquierdo ni a la derecha del corte derecho, así que todas sus copias están dentro de la pieza y esta es una parte válida. Y cualquier respuesta válida solo puede cortar en espacios permitidos, así que ninguna respuesta tiene más partes.

Así que comprueba cada espacio: reúne las letras de su izquierda y de su derecha, y corta si los dos conjuntos no comparten ninguna. En abacdcefe, el espacio después de aba tiene a y b a la izquierda, y c, d, e y f a la derecha. No comparten ninguna, así que haces un corte. El espacio después de ab tiene una a a ambos lados, así que no haces ningún corte.

Cada comprobación lee la cadena entera y hay n-1 espacios, así que se leen aproximadamente n² letras. Con 50,000 letras, eso supone 2.5 × 10^9 lecturas, demasiado lento para los casos de prueba más grandes.

Algoritmo

Establece start = 0, donde comienza la parte actual.
Para cada separación cut desde 1 hasta n-1 (la separación justo antes de s[cut]), marca las letras de s[0..cut-1] y las letras de s[cut..n-1].
Si no hay ninguna letra marcada en ambos lados, añade cut-start a la respuesta y establece start = cut.
Después del bucle, añade la última parte, n-start.

def partitionLabels(s):
    n = len(s)
    sizes = []
    start = 0  # where the current part begins
    for cut in range(1, n):  # the gap just before s[cut]
        left = set(s[:cut])
        right = set(s[cut:])
        if not (left & right):  # no letter on both sides: cut here
            sizes.append(cut - start)
            start = cut
    sizes.append(n - start)  # the last part has no gap after it
    return sizes

Combina el intervalo de cada letra

Intuición

Piensa en cada letra como un intervalo, desde su primera posición hasta la última. Una parte que contiene una letra debe cubrir todo ese intervalo. Así que dos letras cuyos intervalos se superponen deben compartir una parte, y la superposición se extiende: si a se superpone con b y b se superpone con c, las tres terminan en una sola parte.

Ese es el problema de combinar intervalos. Registra la primera y la última posición de cada letra en una pasada. Después, toma los intervalos en el orden en que empiezan y combina los que se superponen. Cada bloque combinado es una parte, y los espacios entre bloques son exactamente los cortes permitidos. Obtienes los intervalos en orden de inicio sin ordenar: recorre la cadena otra vez y toma el intervalo de una letra cuando estés en su primera posición.

En codingisfun, los intervalos en orden son c [0, 0], o [1, 1], d [2, 2], i [3, 6], n [4, 10], g [5, 5], s [7, 7], f [8, 8] y u [9, 9]. Los tres primeros quedan separados. A partir de i, todos los intervalos empiezan en 10 o antes, donde termina n, así que se combinan en [3, 10], una parte de 8 letras.

La cadena tiene como máximo 26 letras diferentes, así que hay como máximo 26 intervalos, y las tablas de primeras y últimas posiciones tienen un tamaño fijo.

Algoritmo

En un recorrido de s, registra first y last, la primera y la última posición de cada letra.
Recorre s de nuevo. Cuando la posición i es la primera posición de su letra, el intervalo de esa letra [i, last] es el siguiente en el orden de inicio.
Si el intervalo comienza después del end del bloque actual, cierra el bloque, de longitud end-start+1, e inicia un bloque nuevo en i.
En cualquier caso, establece end = max(end, last).
Cierra el bloque final y devuelve las longitudes.

def partitionLabels(s):
    first, last = {}, {}
    for i, c in enumerate(s):
        first.setdefault(c, i)
        last[c] = i
    sizes = []
    start = end = 0  # the block of merged spans being built
    for i, c in enumerate(s):
        if first[c] != i:
            continue  # take each letter's span once, at its first position
        if i > end:  # this span starts after the block: close the block
            sizes.append(end - start + 1)
            start = i
        end = max(end, last[c])
    sizes.append(end - start + 1)
    return sizes

Amplía cada parte hasta su última letra

Intuición

Las primeras posiciones no se necesitan en absoluto. Lee la cadena de izquierda a derecha y mantén end, la última posición más lejana de cualquier letra en la parte actual. Cuando leas una letra en i, su última aparición también debe estar en esta parte, así que extiende end hasta last[s[i]] si esa posición está más lejos.

Cuando i llega a end, todas las letras que has leído en esta parte tienen su última aparición en i o antes. Ninguna letra cruza el espacio después de i, así que se permite hacer un corte ahí. Cierra la parte, de longitud end-start+1, y empieza la siguiente en i+1.

¿Por qué cortar en la primera oportunidad es la elección voraz correcta? Antes de que i llegue a end, alguna letra de la parte todavía tiene una aparición más adelante, así que no se permite ningún corte anterior. Y el recorrido nunca pasa por alto un espacio donde se permita un corte: si ninguna letra cruza el espacio después de i, todas las letras de la parte terminan en i o antes, así que end es igual a i justo ahí. El recorrido corta exactamente en los espacios permitidos, lo que da el mayor número posible de partes.

En abacdcefe, las últimas posiciones son a 2, b 1, c 5, d 4, e 8 y f 7. Al leer a, end pasa a ser 2; b lo deja ahí y, en i = 2, la parte se cierra con longitud 3. La c establece end en 5 y la parte se cierra en 5, de nuevo con longitud 3. La parte de e se cierra en 8.

Algoritmo

En un solo recorrido, almacena last[c], la última posición de cada letra c, en un arreglo de 26 elementos.
Establece start = 0 y end = 0.
Para cada posición i, establece end = max(end, last[s[i]]).
Si i == end, suma end-start+1 a la respuesta y establece start = i+1.
Devuelve las longitudes.

def partitionLabels(s):
    last = {c: i for i, c in enumerate(s)}  # last position of each letter
    sizes = []
    start = end = 0
    for i, c in enumerate(s):
        end = max(end, last[c])  # the part must reach c's last copy
        if i == end:  # no letter of this part appears later
            sizes.append(end - start + 1)
            start = i + 1
    return sizes

Errores comunes y casos límite

El recorrido codicioso es corto, así que los errores se esconden en la posición con la que comparas y en las longitudes de las partes.

Cortar al llegar a la última aparición de la letra actual en vez de al end de la parte. En abcba, la c en el índice 2 es su última aparición, pero las a llegan hasta el índice 4, así que cortar ahí dividiría tanto las a como las b.
Un error de una unidad en la longitud. Una parte desde start hasta end, ambos incluidos, tiene end-start+1 letras.
Devolver las posiciones de corte en vez de las longitudes. Para abacdcefe, la respuesta es [3, 3, 3], no [2, 5, 8].
Olvidar la última parte cuando cortas en los espacios. La parte final no tiene ningún espacio después, así que suma n-start cuando termine el bucle.
Esperar una parte por cada letra distinta. zebraz tiene cinco letras diferentes y una sola parte, porque las z mantienen unido todo lo que hay entre ellas.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de Partition Labels?

Una pasada registra la última posición de cada letra y una segunda pasada coloca los cortes, por lo que el tiempo es O(n). La tabla de últimas posiciones tiene 26 entradas independientemente de la longitud de la cadena, por lo que el espacio adicional es O(1), sin contar la salida.

¿Por qué funciona el enfoque voraz para la partición de etiquetas?

La parte actual debe llegar a la última copia de cada letra que contiene, así que no se permite ningún corte antes de end. En end no aparece después ninguna letra de la parte, así que se permite el corte, y hacerlo nunca perjudica al resto de la cadena. Por lo tanto, el recorrido corta en cada espacio permitido y en ningún otro, lo que da el mayor número de partes que puede tener cualquier respuesta.

¿Es Partition Labels un problema de fusión de intervalos?

Sí, de forma encubierta. Cada letra abarca el intervalo desde su primera aparición hasta la última; los intervalos que se superponen deben compartir una parte, y al fusionarlos se obtienen exactamente las partes. El recorrido voraz es la misma fusión hecha sobre la marcha: end es el borde derecho del bloque fusionado hasta el momento.

¿Cuántas partes puede devolver Partition Labels?

Entre 1 y 26. Ninguna letra puede aparecer en dos partes, así que cada parte tiene al menos una letra propia, y solo hay 26 letras minúsculas. Una cadena con cada letra una vez da 26 partes de longitud 1, y una cadena que empieza y termina con la misma letra da una sola parte.

Python

def partitionLabels(s):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

s = "abacdcefe"

Esperado

[3, 3, 3]

Partition Labels

Función

Restricciones

Ejemplos

Pistas

Solución

Prueba cada espacio en blanco

Combina el intervalo de cada letra

Amplía cada parte hasta su última letra

Errores comunes y casos límite

Preguntas frecuentes4

Problemas similares