Partition Labels

+10

Você recebe uma string s de letras minúsculas. Divida-a no maior número possível de partes consecutivas, de modo que cada letra apareça em apenas uma parte: se uma letra aparecer em uma parte, todas as suas ocorrências estarão nessa parte. Retorne os comprimentos das partes da esquerda para a direita.

Função

partitionLabels(s: string) → integer-array

sstring: o texto a ser cortado, somente letras minúsculas
Retornainteger-array: o comprimento de cada parte, da esquerda para a direita

Restrições

1 ≤ s.length ≤ 5 × 10⁴
s contém apenas letras minúsculas do inglês.
As partes mantêm sua ordem e, juntas, compõem todo o s, então os comprimentos somam s.length.

Exemplos

Entrada: s = "abacdcefe"
Saída: [3, 3, 3]
Explicação: Os a's ficam nas posições 0 e 2, os c's nas posições 3 e 5 e os e's nas posições 6 e 8, então os cortes ficam depois de aba e depois de cdc. Nenhuma parte pode ser cortada novamente, porque cada uma começa e termina com a mesma letra.

+14 testes ocultos ao enviar

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Um corte só é permitido onde nenhuma letra aparece nos dois lados, e a melhor resposta faz um corte em cada lugar desse tipo. Testar cada lugar percorrendo a string novamente leva tempo quadrático. Primeiro, registre a última posição de cada letra; depois, uma única passagem da esquerda para a direita encontra todos os cortes, pois uma parte precisa se estender até a última ocorrência de cada letra que esteja dentro dela.

Teste cada lacuna

Correta, mas não termina nos maiores testes

Intuição

Há n-1 lacunas entre letras vizinhas. Um corte em uma lacuna só é permitido quando nenhuma letra aparece dos dois lados, pois uma letra dividida pelo corte ficaria em duas partes. Fazer todos os cortes permitidos resulta no maior número de partes. Considere um trecho entre dois cortes permitidos vizinhos: nenhuma de suas letras aparece à esquerda do corte da esquerda nem à direita do corte da direita, então todas as suas cópias estão dentro do trecho, que é uma parte válida. E qualquer resposta válida só pode cortar em lacunas permitidas, então nenhuma resposta tem mais partes.

Então teste cada lacuna: reúna as letras à esquerda e à direita e corte se os dois conjuntos não tiverem nada em comum. Em abacdcefe, a lacuna depois de aba tem a e b à esquerda e c, d, e e f à direita. Não há letras em comum, então você corta. A lacuna depois de ab tem um a dos dois lados, então você não corta.

Cada teste percorre a string inteira, e há n-1 lacunas, então o trabalho envolve cerca de n² leituras de letras. Com 50.000 letras, são 2.5 × 10^9 leituras, muito lento para os maiores testes.

Algoritmo

Defina start = 0, onde a parte atual começa.
Para cada separação cut de 1 a n-1 (a separação logo antes de s[cut]), marque as letras de s[0..cut-1] e as letras de s[cut..n-1].
Se nenhuma letra estiver marcada nos dois lados, adicione cut-start à resposta e defina start = cut.
Após o loop, adicione a ú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

Combine o intervalo de cada letra

Intuição

Pense em cada letra como um intervalo, da primeira à última posição em que aparece. Uma parte que contém uma letra precisa cobrir todo esse intervalo. Portanto, duas letras cujos intervalos se sobrepõem precisam ficar na mesma parte, e a sobreposição se propaga: se a se sobrepõe a b e b se sobrepõe a c, as três acabam na mesma parte.

Esse é o problema de mesclar intervalos. Registre a primeira e a última posição de cada letra em uma única passagem. Depois, percorra os intervalos na ordem em que começam e mescle os que se sobrepõem. Cada bloco mesclado é uma parte, e os espaços entre os blocos são exatamente os cortes permitidos. Você obtém os intervalos na ordem de início sem ordenar: percorra a string novamente e pegue o intervalo de uma letra quando estiver na posição em que ela aparece pela primeira vez.

Em codingisfun, os intervalos em ordem são 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]. As três primeiras letras ficam sozinhas. A partir de i, cada intervalo começa na posição 10 ou antes, onde termina n, então eles se mesclam em [3, 10], uma parte com 8 letras.

A string tem no máximo 26 letras diferentes, então há no máximo 26 intervalos, e as tabelas de primeiras e últimas posições têm tamanho fixo.

Algoritmo

Em uma única passagem por s, registre first e last, a primeira e a última posição de cada letra.
Percorra s novamente. Quando a posição i for a primeira posição da letra correspondente, o intervalo dessa letra, [i, last], será o próximo na ordem de início.
Se o intervalo começar depois do end do bloco atual, feche o bloco, com comprimento end-start+1, e comece um novo bloco em i.
De qualquer forma, defina end = max(end, last).
Feche o bloco final e retorne os comprimentos.

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

Expanda cada parte até sua última letra

Intuição

As primeiras posições não são necessárias. Leia a string da esquerda para a direita e mantenha end, a posição mais distante da última ocorrência de qualquer letra na parte atual. Ao ler uma letra em i, sua última ocorrência também precisa estar nesta parte, então estenda end até last[s[i]] se essa posição for mais distante.

Quando i chega a end, a última ocorrência de cada letra lida nesta parte está em i ou antes. Nenhuma letra atravessa o intervalo após i, então é permitido cortar ali. Feche a parte, de comprimento end-start+1, e comece a próxima em i+1.

Por que cortar na primeira oportunidade é a escolha gulosa correta? Antes de i chegar a end, alguma letra da parte ainda tem uma ocorrência mais à direita, então nenhum corte anterior é permitido. E a passagem nunca deixa passar um intervalo permitido: se nenhuma letra atravessa o intervalo após i, a última ocorrência de cada letra da parte está em i ou antes, então end é igual a i exatamente ali. A passagem corta exatamente nos intervalos permitidos, o que produz o maior número possível de partes.

Em abacdcefe, as últimas posições são a 2, b 1, c 5, d 4, e 8 e f 7. Ler a define end como 2, b o mantém nesse valor e, em i = 2, a parte se fecha com comprimento 3. O c define end como 5 e a parte se fecha em 5, novamente com comprimento 3. A parte com e se fecha em 8.

Algoritmo

Em uma única passagem, armazene last[c], a última posição de cada letra c, em um array de 26 elementos.
Defina start = 0 e end = 0.
Para cada posição i, defina end = max(end, last[s[i]]).
Se i == end, adicione end-start+1 à resposta e defina start = i+1.
Retorne os comprimentos.

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

Armadilhas e casos extremos

A etapa gulosa é curta, então os bugs ficam escondidos na posição com a qual você compara e nos comprimentos das partes.

Cortar quando você chega à última ocorrência da letra atual, em vez de chegar ao end da parte. Em abcba, o c no índice 2 é sua própria última ocorrência, mas os a's vão até o índice 4, então um corte ali dividiria tanto os a's quanto os b's.
Erro de uma unidade no comprimento. Uma parte de start a end, incluindo ambos, tem end-start+1 letras.
Retornar as posições dos cortes em vez dos comprimentos. Para abacdcefe, a resposta é [3, 3, 3], não [2, 5, 8].
Esquecer a última parte ao cortar nos intervalos. A última parte não tem um intervalo depois dela, então adicione n-start quando o loop terminar.
Esperar uma parte por letra distinta. zebraz tem cinco letras diferentes e uma única parte, porque os z's mantêm tudo entre eles unido.

Perguntas frequentes4

Qual é a complexidade de tempo de Partition Labels?

Uma passagem registra a última posição de cada letra, e uma segunda passagem determina os cortes, portanto, o tempo é O(n). A tabela de últimas posições tem 26 entradas, independentemente do comprimento da string, então o espaço extra é O(1), sem contar a saída.

Por que a abordagem gulosa funciona para Partition Labels?

A parte atual precisa chegar à última ocorrência de cada letra que contém, então nenhum corte antes de end é permitido. Em end, nenhuma letra da parte aparece mais adiante, então o corte é permitido, e fazê-lo nunca prejudica o restante da string. Portanto, a passagem corta em cada intervalo permitido e em nenhum outro, o que resulta no maior número de partes possível.

O problema Partition Labels é um problema de mesclagem de intervalos?

Sim, de forma disfarçada. Cada letra cobre o intervalo entre sua primeira ocorrência e sua última, intervalos sobrepostos precisam compartilhar uma parte, e mesclá-los resulta exatamente nas partes. A passagem gulosa é a mesma mesclagem feita em tempo real: end é a borda direita do bloco mesclado até então.

Quantas partes Partition Labels pode retornar?

Entre 1 e 26. Nenhuma letra pode aparecer em duas partes, então cada parte possui pelo menos uma letra própria, e há apenas 26 letras minúsculas. Uma string com cada letra aparecendo uma vez resulta em 26 partes de comprimento 1, e uma string que começa e termina com a mesma letra resulta em uma única parte.

Python

def partitionLabels(s):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

s = "abacdcefe"

Esperado

[3, 3, 3]

Partition Labels

Função

Restrições

Exemplos

Dicas

Solução

Teste cada lacuna

Combine o intervalo de cada letra

Expanda cada parte até sua última letra

Armadilhas e casos extremos

Perguntas frequentes4

Problemas parecidos