String Compression

Q: Qual é a complexidade de tempo da compactação de strings?

A varredura com dois ponteiros leva O(n) de tempo, porque o índice de varredura só avança. Além do resultado, ela mantém dois índices, então o espaço extra é O(1) .

FácilDois ponteiros Arrays e strings

+10

Você recebe uma string s de letras do alfabeto inglês. Comprima-a: substitua cada sequência de duas ou mais letras iguais consecutivas por essa letra seguida pelo comprimento da sequência, e mantenha uma letra que aparece sozinha como está. Assim, aabccc se torna a2bc3. Retorne a string comprimida.

Letras maiúsculas e minúsculas são diferentes: aA são duas sequências de comprimento 1.

Função

compress(s: string) → string

sstring: a string a ser compactada, somente letras do alfabeto inglês
Retornastring: a string compactada, cada sequência escrita como sua letra seguida de seu comprimento quando o comprimento for maior que 1

Restrições

1 ≤ s.length ≤ 2 × 10⁴
s contém apenas letras do alfabeto inglês, de a a z e de A a Z.
Um comprimento de sequência é escrito em decimal e pode ter vários dígitos.

Exemplos

Entrada: s = "aabccc"
Saída: "a2bc3"
Explicação: As sequências são aa, b e ccc. Elas se tornam a2, b (uma letra isolada não recebe contagem) e c3.

Entrada: s = "abbbbbbbbbbbb"
Saída: "ab12"
Explicação: Um a, depois doze b. O comprimento 12 é escrito com os dois caracteres 1 e 2, então o resultado é ab12.

Entrada: s = "zzZZZ"
Saída: "z2Z3"
Explicação: As letras minúscula z e maiúscula Z são diferentes, então esta é uma sequência de duas seguida por uma sequência de três: z2Z3.

Para ir além

Faça o inverso: dada uma string comprimida como ab12, reconstrua a original. Como você lê uma contagem com vários dígitos?

Dicas

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

0 de 3 abertas

Solução

Encontre onde cada sequência de letras iguais começa e termina, depois escreva seu comprimento como texto. Uma sequência de uma letra não recebe contagem, e uma contagem pode ter vários dígitos. Dois índices, um no início de uma sequência e outro percorrendo-a até o fim, fazem isso em uma única passagem.

Reúna as corridas e, em seguida, escreva-as

Intuição

Primeiro, registre as sequências como pares de uma letra e um comprimento: para aabccc, (a, 2), (b, 1), (c, 3). Cada letra estende a última sequência ou inicia uma nova. Em seguida, escreva a letra de cada sequência, seguida pelo seu comprimento quando for maior que 1.

Ambas as passagens são O(n). A lista pode conter n sequências quando dois caracteres vizinhos nunca são iguais, então isso custa O(n) de espaço extra.

Algoritmo

Crie uma lista vazia de sequências.
Para cada letra de s: se a última sequência tiver a mesma letra, some 1 ao seu comprimento; caso contrário, acrescente uma nova sequência de comprimento 1.
Para cada sequência, escreva sua letra e, em seguida, seu comprimento como texto decimal se o comprimento for maior que 1.

def compress(s):
    # First pass: collect the runs as [letter, length] pairs
    runs = []
    for ch in s:
        if runs and runs[-1][0] == ch:
            runs[-1][1] += 1
        else:
            runs.append([ch, 1])
    # Second pass: write each run, with its length when it is more than 1
    parts = []
    for letter, length in runs:
        parts.append(letter)
        if length > 1:
            parts.append(str(length))
    return "".join(parts)

Dois ponteiros sobre cada sequência

Intuição

Mantenha i na primeira letra do trecho atual e avance j enquanto s[j] for igual a s[i]. Quando j parar, em uma letra diferente ou no fim, o comprimento do trecho será j-i. Escreva-o e defina i = j. Em abbbbbbbbbbbb, j para primeiro em 1, gerando a, e depois em 13, gerando b12.

O último trecho não precisa de um caso especial, porque o loop interno para no fim da string. j só avança, então o tempo é O(n) e, além do resultado, você mantém dois índices. As versões em R e Swift dividem s primeiro em um array de caracteres, então usam O(n) de espaço extra.

Algoritmo

Defina i = 0.
Enquanto i estiver dentro da string, defina j = i e avance j enquanto ele estiver dentro da string e s[j] for igual a s[i].
Escreva s[i]; se j-i for maior que 1, escreva-o como texto decimal.
Defina i = j e repita.

def compress(s):
    parts = []
    n = len(s)
    i = 0
    while i < n:
        # Move j to the first index after the run that starts at i
        j = i
        while j < n and s[j] == s[i]:
            j += 1
        parts.append(s[i])
        if j - i > 1:
            parts.append(str(j - i))
        i = j
    return "".join(parts)

Armadilhas e casos extremos

Escrever uma sequência somente quando você encontra uma letra diferente. Nada vem depois do ccc final de aabccc, então você retorna a2b.
Escrever a contagem como um caractere, como em '0' + count. Isso falha em 10: doze bs precisam dos dois caracteres 12.
Escrever 1 depois de uma letra isolada. b continua sendo b, não b1.
Ignorar maiúsculas e minúsculas. zzZZZ é z2Z3, não z5.
Ampliar uma string imutável usando +, como em Java ou C#. Cada + copia o resultado até então, o que torna o loop O(n²); use um construtor de strings.

Perguntas frequentes3

Qual é a complexidade de tempo da compactação de strings?

A varredura com dois ponteiros leva O(n) de tempo, porque o índice de varredura só avança. Além do resultado, ela mantém dois índices, então o espaço extra é O(1).

A string compactada pode ser mais longa que a original?

Não nesta versão. Uma letra isolada continua sendo um caractere, e uma sequência de k ≥ 2 letras se transforma em uma letra mais os dígitos de k, nunca mais do que k caracteres. Um esquema que escreve uma contagem após cada letra, como a1b1, pode dobrar o comprimento.

Como você comprime uma string no próprio lugar?

Use um array de caracteres com um índice de leitura e um índice de escrita. Percorra cada sequência com o índice de leitura e, em seguida, escreva sua letra e os dígitos de seu comprimento no índice de escrita. A saída nunca é mais longa do que a entrada lida até então, portanto o índice de escrita nunca ultrapassa o índice de leitura. Retorne o novo comprimento ao final.

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

Teste #1

Teste #2

Teste #3

Argumento

s = "aabccc"

Saída Esperada

"a2bc3"