Partition Labels

+10

Hai una stringa s composta da lettere minuscole. Dividila nel maggior numero possibile di parti consecutive, in modo che ogni lettera compaia in una sola parte: se una lettera compare in una parte, tutte le sue occorrenze si trovano in quella parte. Restituisci le lunghezze delle parti da sinistra a destra.

Funzione

partitionLabels(s: string) → integer-array

sstring: la stringa da tagliare, solo lettere minuscole
Restituisceinteger-array: la lunghezza di ciascuna parte, da sinistra a destra

Vincoli

1 ≤ s.length ≤ 5 × 10⁴
s contiene solo lettere inglesi minuscole.
Le parti mantengono il loro ordine e insieme compongono tutto s, quindi le lunghezze sommate danno s.length.

Esempi

Input: s = "abacdcefe"
Output: [3, 3, 3]
Spiegazione: Le a si trovano alle posizioni 0 e 2, le c alle posizioni 3 e 5 e le e alle posizioni 6 e 8, quindi i tagli cadono dopo aba e dopo cdc. Nessuna parte può essere tagliata di nuovo, perché ciascuna inizia e finisce con la stessa lettera.

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Un taglio è consentito solo dove non compare alcuna lettera da entrambi i lati, e la risposta migliore prevede un taglio in ogni punto di questo tipo. Verificare ogni punto riesaminando la stringa richiede un tempo quadratico. Registra prima l'ultima posizione di ogni lettera: basta poi un'unica passata da sinistra a destra per trovare tutti i tagli, perché una parte deve estendersi fino all'ultima occorrenza di ogni lettera al suo interno.

Verifica ogni spazio vuoto

Corretto, ma non termina sui test più grandi

Intuizione

Ci sono n-1 spazi tra lettere adiacenti. È consentito tagliare in uno spazio solo quando nessuna lettera compare su entrambi i lati, perché una lettera divisa dal taglio si troverebbe in due parti. Effettuare tutti i tagli consentiti dà il maggior numero di parti. Prendi un pezzo compreso tra due tagli consentiti adiacenti: nessuna delle sue lettere compare a sinistra del taglio sinistro o a destra del taglio destro, quindi tutte le loro copie si trovano all'interno del pezzo, che è una parte valida. E qualsiasi risposta valida può tagliare solo negli spazi consentiti, quindi nessuna risposta può avere più parti.

Quindi controlla ogni spazio: raccogli le lettere alla sua sinistra e alla sua destra e taglia se i due insiemi non hanno elementi in comune. In abacdcefe lo spazio dopo aba ha a e b a sinistra e c, d, e e f a destra. Non c'è niente in comune, quindi tagli. Lo spazio dopo ab ha una a su entrambi i lati, quindi non tagli.

Ogni controllo legge l'intera stringa e ci sono n-1 spazi, quindi il lavoro richiede circa n² letture di lettere. Con 50.000 lettere sono 2.5 × 10^9 letture, troppo lento per i test più grandi.

Algoritmo

Imposta start = 0, dove inizia la parte corrente.
Per ogni punto di divisione cut da 1 a n-1 (il punto subito prima di s[cut]), contrassegna le lettere di s[0..cut-1] e le lettere di s[cut..n-1].
Se nessuna lettera è contrassegnata su entrambi i lati, aggiungi cut-start alla risposta e imposta start = cut.
Dopo il ciclo, aggiungi l'ultima 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

Unisci l'intervallo di ogni lettera

Intuizione

Pensa a ogni lettera come a un intervallo, dalla sua prima posizione all’ultima. Una parte che contiene una lettera deve coprire l’intero intervallo. Quindi due lettere i cui intervalli si sovrappongono devono appartenere alla stessa parte, e la sovrapposizione si propaga: se a si sovrappone a b e b si sovrappone a c, tutte e tre finiscono nella stessa parte.

Questo è il problema dell’unione degli intervalli. Registra la prima e l’ultima posizione di ogni lettera in un unico passaggio. Poi considera gli intervalli nell’ordine in cui iniziano e unisci quelli che si sovrappongono. Ogni blocco unito è una parte, e gli spazi tra i blocchi sono esattamente i punti in cui è consentito tagliare. Ottieni gli intervalli in ordine di inizio senza ordinare: percorri di nuovo la stringa e considera l’intervallo di una lettera quando ti trovi nella sua prima posizione.

In codingisfun, gli intervalli in ordine sono c [0, 0], o [1, 1], d [2, 2], i [3, 6], n [4, 10], g [5, 5], s [7, 7], f [8, 8] e u [9, 9]. I primi tre restano separati. A partire da i, ogni intervallo inizia in corrispondenza o prima di 10, dove termina n, quindi si uniscono in [3, 10], una parte di 8 lettere.

La stringa contiene al massimo 26 lettere diverse, quindi ci sono al massimo 26 intervalli, e le tabelle delle prime e ultime posizioni hanno dimensione fissa.

Algoritmo

In un'unica scansione di s, registra first e last, la prima e l'ultima posizione di ogni lettera.
Scorri di nuovo s. Quando la posizione i è la prima posizione della sua lettera, l'intervallo di quella lettera [i, last] è il successivo nell'ordine di inizio.
Se l'intervallo inizia dopo end del blocco corrente, chiudi il blocco, di lunghezza end-start+1, e avvia un nuovo blocco in corrispondenza di i.
In entrambi i casi, imposta end = max(end, last).
Chiudi il blocco finale e restituisci le lunghezze.

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

Fai crescere ogni parte fino alla sua ultima lettera

Intuizione

Le prime posizioni non servono affatto. Leggi la stringa da sinistra a destra e mantieni end, la posizione più lontana a destra dell’ultima occorrenza di qualsiasi lettera nella parte corrente. Quando leggi una lettera in i, anche la sua ultima occorrenza deve trovarsi in questa parte, quindi estendi end a last[s[i]] se è più lontano.

Quando i raggiunge end, ogni lettera letta in questa parte ha la sua ultima occorrenza in i o prima. Nessuna lettera oltrepassa il confine dopo i, quindi è consentito tagliare lì. Chiudi la parte, di lunghezza end-start+1, e inizia la successiva da i+1.

Perché tagliare alla prima occasione è la scelta greedy corretta? Prima che i raggiunga end, qualche lettera della parte ha ancora un’occorrenza più a destra, quindi non è consentito alcun taglio precedente. Inoltre, il passaggio non si lascia sfuggire nessun punto di taglio consentito: se nessuna lettera oltrepassa il confine dopo i, ogni lettera della parte termina entro i, quindi proprio lì end è uguale a i. Il passaggio taglia esattamente nei punti consentiti, ottenendo il maggior numero possibile di parti.

In abacdcefe le ultime posizioni sono a 2, b 1, c 5, d 4, e 8 e f 7. Leggere a imposta end a 2, b lo lascia invariato e, a i = 2, la parte si chiude con lunghezza 3. La c imposta end a 5 e la parte si chiude a 5, ancora con lunghezza 3. La parte che contiene e si chiude a 8.

Algoritmo

In un'unica passata, memorizza last[c], l'ultima posizione di ogni lettera c, in un array di 26 elementi.
Imposta start = 0 e end = 0.
Per ogni posizione i, imposta end = max(end, last[s[i]]).
Se i == end, aggiungi end-start+1 alla risposta e imposta start = i+1.
Restituisci le lunghezze.

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

Trappole e casi limite

La passata greedy è breve, quindi i bug si nascondono nella posizione con cui fai il confronto e nella lunghezza delle parti.

Tagliare quando raggiungi l'ultima occorrenza della lettera corrente invece che l'end della parte. In abcba, la c all'indice 2 è la sua ultima occorrenza, ma le a arrivano fino all'indice 4, quindi un taglio lì separerebbe sia le a sia le b.
Errore di un'unità nella lunghezza. Una parte da start a end, estremi inclusi, ha end-start+1 lettere.
Restituire le posizioni dei tagli invece delle lunghezze. Per abacdcefe, la risposta è [3, 3, 3], non [2, 5, 8].
Dimenticare l'ultima parte quando tagli in corrispondenza degli spazi. Dopo l'ultima parte non c'è alcuno spazio, quindi aggiungi n-start una volta terminato il ciclo.
Aspettarsi una parte per ogni lettera distinta. zebraz ha cinque lettere diverse e una sola parte, perché le z tengono insieme tutto ciò che c'è tra loro.

Domande frequenti3

Qual è la complessità temporale di Partition Labels?

Una passata registra l’ultima posizione di ogni lettera e una seconda passata posiziona i tagli, quindi il tempo è O(n). La tabella delle ultime posizioni ha 26 voci indipendentemente dalla lunghezza della stringa, quindi lo spazio aggiuntivo è O(1), senza contare l’output.

Perché l’approccio greedy funziona per le etichette di partizione?

La parte corrente deve raggiungere l’ultima occorrenza di ogni lettera che contiene, quindi non è consentito alcun taglio prima di end. In end non compare più nessuna lettera della parte, quindi il taglio è consentito e farlo non danneggia mai il resto della stringa. Il passaggio taglia quindi in ogni punto consentito e in nessun altro, ottenendo il maggior numero di parti possibile.

Partition Labels è un problema di fusione di intervalli?

Sì, sotto mentite spoglie. Ogni lettera copre l’intervallo dalla sua prima occorrenza all’ultima, gli intervalli sovrapposti devono condividere una parte e unirli dà esattamente le parti. Il passaggio greedy è la stessa unione eseguita al volo: end è il bordo destro del blocco unito fino a quel momento.

def partitionLabels(s):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomento

s = "abacdcefe"

Output atteso

[3, 3, 3]

Partition Labels

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Verifica ogni spazio vuoto

Unisci l'intervallo di ogni lettera

Fai crescere ogni parte fino alla sua ultima lettera

Trappole e casi limite

Domande frequenti3

Problemi simili