Strings

A string é um array com uma regra a mais

Na memória, uma string é o que um array é: uma sequência contígua de posições do mesmo tamanho. Em C isso era explícito, você declarava um char[] e terminava com o byte zero. As linguagens modernas embrulharam esse array num tipo chamado string e a origem ficou escondida, mas ela continua lá embaixo.

Como as posições têm tamanho fixo e ficam grudadas, o acesso por índice é uma conta de endereço, não uma busca:

s = "CCC"
s[0]     # 'C' em O(1): endereco_base + 0 * tamanho_do_elemento
s[2]     # 'C' em O(1) também, não importa o tamanho da string
len(s)   # O(1): o tamanho fica guardado no objeto

Esse len em O(1) é herança de ter um cabeçalho. Em C, strlen é O(n): sem cabeçalho, a única forma de saber o tamanho é caminhar até achar o byte zero. É a mesma diferença entre um array que sabe o próprio tamanho e um que não sabe.

A "regra a mais" do título são duas, e as duas quebram a intuição de quem vem do array:

O caractere é um número, e é por isso que ele vira índice

Por baixo do glifo existe um número, o code point. ord("a") devolve 97, chr(97) devolve "a", e as 26 minúsculas do alfabeto inglês são 97 até 122, em sequência. É essa sequência que transforma um caractere numa posição de array:

ord("a")               # 97
ord("c") - ord("a")    # 2  <- "c" é a terceira letra, índice 2

Daí sai a ferramenta mais usada em problema de string, o contador de frequência:

def contar(s):
    freq = [0] * 26                    # uma posição por letra minúscula
    for c in s:
        freq[ord(c) - ord("a")] += 1   # O(1) por caractere
    return freq

def sao_anagramas(a, b):
    return len(a) == len(b) and contar(a) == contar(b)

Uma passada só: O(n) em tempo, e O(1) em espaço extra, porque são sempre 26 posições, com string de 10 ou de 10 milhões de caracteres. Compare com as duas alternativas óbvias: ordenar as duas strings e comparar é O(n log n), e chamar s.count(c) dentro de um laço é O(n²), porque cada count percorre a string inteira de novo.

Um caractere não é um byte

Comece pelo caso simples. Em ASCII cada caractere ocupa 1 byte e existem 128 deles, o que cobre o alfabeto inglês, os dígitos e a pontuação. "CCC" são 3 bytes, e ponto.

Agora rode a mesma string nos outros encodings. No visualizador abaixo, o padrão já é CCC: repare que ASCII e UTF-8 dão 3 bytes, UTF-16 dá 6 e UTF-32 dá 12. É exatamente o que o Encoding.ASCII.GetBytes, o Encoding.Unicode.GetBytes e o Encoding.UTF32.GetBytes devolvem em C#.

Clique nos exemplos, um por um, e acompanhe os quatro contadores de cima:

• ção: 3 caracteres, mas 5 bytes em UTF-8, porque ç e ã custam 2 bytes cada. Em ASCII os dois viram ? e a informação some. É a mesma história do SMS que contava mais caracteres quando você escrevia com cedilha.
• 日本語: 3 caracteres, 9 bytes em UTF-8 (3 cada) e 6 em UTF-16. Aqui o UTF-16 é mais econômico que o UTF-8, o que costuma surpreender.
• família: o campeão. São 7 code points (quatro pessoas e três "colas" invisíveis, o ZWJ), 11 unidades UTF-16 e 25 bytes em UTF-8, para 1 coisa só na tela.

O emoji da família é o exemplo que vale guardar: em C#, "👨‍👩‍👧‍👦".Length devolve 11, porque Length conta unidades UTF-16. new StringInfo(s).LengthInTextElements devolve 1, porque conta o que a pessoa vê. No Python, len devolve 7, porque conta code points. Nenhum dos três está errado, eles respondem a perguntas diferentes.

Imutável: o que isso cobra e o que isso paga

Em Python, C#, Java, JavaScript e Go, a string é imutável. Tentar escrever numa posição não compila ou explode:

s = "CCC"
s[0] = "c"
# TypeError: 'str' object does not support item assignment

Em PHP e em Ruby, a mesma linha funciona: lá a string é mutável e se comporta como o array de caracteres que ela sempre foi por baixo. Ou seja, "string é imutável" não é uma lei da computação, é uma escolha de projeto da linguagem.

E é uma escolha com motivo. Uma string imutável pode ser compartilhada entre threads sem lock nenhum, porque ninguém consegue mudá-la debaixo do outro. Pode ser usada como chave de dicionário com o hash calculado uma vez e guardado. Pode ser passada para uma função sem cópia defensiva, sem medo de voltar diferente.

A conta desse benefício chega na hora de "alterar":

s = "CCC"
t = s           # duas referências para a MESMA string
s += "!"        # não alterou a string: criou outra e apontou s para ela
print(s, t)     # CCC! CCC  <- t continua intacto

Nada foi acrescentado ao fim de "CCC", tanto que t não mudou. O runtime alocou espaço para 4 caracteres, copiou os 3 antigos, escreveu o ! e moveu a referência de s. A string velha ficou para trás, esperando o coletor de lixo. Faça isso uma vez e não custa nada. Faça num laço e a conta muda de família.

O laço que concatena, e o O(n²) escondido

Concatenar duas strings de tamanhos n e m custa O(n + m) em tempo e em espaço: aloca uma string nova de n + m e copia as duas para dentro dela. O código do String.Concat do .NET é literalmente isso: mede os dois tamanhos, aloca o total, copia a primeira, copia a segunda depois dela, devolve a nova.

O problema não é uma concatenação. É esta:

def juntar(palavra):
    s = ""
    for c in palavra:
        s = s + c     # string NOVA a cada volta
    return s

Na volta 1 copia 1 caractere. Na volta 2 copia 2 (o antigo mais o novo). Na volta 3 copia 3. A soma é 1 + 2 + ... + n, que é n(n+1)/2, ou seja O(n²).

Rode o visualizador abaixo no modo s = s + c. Com o padrão CRAFTCODE, de 9 letras, o contador de caracteres copiados fecha em 45, com 9 strings alocadas, das quais 8 viram lixo. Agora troque para lista + join na mesma palavra: 9 cópias e 1 string. Os dois totais ficam sempre visíveis nos cartões, então dá para acompanhar a distância aumentando enquanto o laço anda.

Olhe também a faixa Memória: no modo s = s + c ela vai acumulando bloco atrás de bloco, e todos menos o último aparecem riscados, que é o lixo esperando o coletor. No modo join, a faixa fica vazia até o último passo, quando aparece um bloco só.

Use os atalhos abaixo do campo (CCC, CRAFTCODE, CRAFTCODECLUB, entrada vazia) ou digite qualquer palavra, e veja a distância explodir. A conta é a mesma para qualquer n:

Com 10 mil caracteres, o laço ingênuo copia 5.000 vezes mais do que o necessário. E o custo não para no tempo: cada volta joga uma string inteira no lixo. Num benchmark simples, a mesma montagem leva 25 segundos com concatenação e fica colada no zero com o builder.

O builder: pagar a cópia uma vez só

A saída é sempre a mesma ideia: adiar a cópia. Em vez de materializar a string a cada volta, guarde os pedaços e junte tudo uma vez.

def juntar(palavra):
    partes = []
    for c in palavra:
        partes.append(c)      # O(1) amortizado, não copia caractere
    return "".join(partes)    # aloca UMA vez e copia tudo numa passada

Cada append é O(1) amortizado, porque a lista é um array dinâmico que dobra de tamanho de vez em quando (o mesmo mecanismo do tópico de Arrays). O join soma os tamanhos, aloca o total exato e copia. Total: O(n).

Cada linguagem tem a sua porta para isso:

Duas finezas que valem saber:

Diga a capacidade quando você souber. new StringBuilder(4096) ou builder.Grow(n) evitam a série de realocações do buffer interno. É o mesmo raciocínio de já criar a lista com o tamanho certo, e a diferença aparece quando o volume é grande.

O builder não é grátis, ele é amortizado. No ToString() ainda existe uma alocação do tamanho final e uma cópia de todos os caracteres. Trocar duas concatenações por um builder não ganha nada, e ainda deixa o código mais feio. Para juntar dois ou três pedaços, use interpolação: f"{nome} tem {idade} anos" no Python, $"..." no C#. No .NET, o compilador transforma a interpolação num handler que já monta a string de uma vez só, e dá para ver isso no código intermediário gerado.

Quando a saída é mais de uma string ao mesmo tempo

O padrão não muda quando você precisa montar k saídas em paralelo, em vez de uma. Use k builders, não k strings. É exatamente o que o Zigzag Conversion pede: distribuir os caracteres em k linhas e depois ler linha por linha.

def zigzag(s, k):
    if k == 1:
        return s                        # sem zigue-zague, a saída é a entrada
    linhas = [[] for _ in range(k)]     # k listas, k builders
    i, passo = 0, 1
    for c in s:
        linhas[i].append(c)             # O(1): cai na linha atual
        if i == 0:
            passo = 1                   # bateu no topo, desce
        elif i == k - 1:
            passo = -1                  # bateu no fundo, sobe
        i += passo
    return "".join("".join(linha) for linha in linhas)

Cada caractere entra em exatamente uma lista e o join final passa uma vez por tudo: O(n) em tempo e O(n) em espaço. Se você trocasse as listas por strings e escrevesse linhas[i] += c, seria o mesmo O(n²) da seção do laço, agora repetido k vezes.

Repare nos dois casos de borda que derrubam a maioria das primeiras submissões: k == 1 (sem o return s, o passo nunca inverte e o índice estoura) e k >= len(s) (o laço nunca chega na última linha, e as linhas vazias somem sozinhas no join).

Vire lista, edite, volte para string

Se uma alteração custa O(n), k alterações custam O(k · n). Quando k cresce junto com n, isso é O(n²) de novo:

# ruim: cada troca recria a string inteira
for i in range(len(s)):
    if s[i] == "a":
        s = s[:i] + "A" + s[i+1:]     # O(n) por troca

O contorno é converter uma vez, mexer à vontade no array de caracteres e converter de volta:

# bom: O(n) para virar lista, O(1) por troca, O(n) para voltar
chars = list(s)
for i in range(len(chars)):
    if chars[i] == "a":
        chars[i] = "A"                # O(1)
s = "".join(chars)

Você pagou 2n de conversão para transformar cada edição em O(1). É o mesmo movimento do builder, aplicado a edição em vez de montagem. Vale a pena sempre que houver mais de um punhado de alterações.

Dois índices no array de caracteres

O caso mais puro dessa conversão é inverter. Em Python dá para escrever s[::-1], que é O(n) em tempo e em espaço, porque aloca a cópia invertida. O Reverse String do LeetCode fecha essa porta de propósito: ele já entrega uma lista de caracteres e exige a troca no lugar.

def reverse(chars):
    e, d = 0, len(chars) - 1
    while e < d:                                   # param quando se cruzam
        chars[e], chars[d] = chars[d], chars[e]    # troca em O(1)
        e += 1
        d -= 1

São n/2 trocas: O(n) em tempo e O(1) em espaço extra. Com lista vazia, e = 0 e d = -1, o laço não roda; com um caractere só, e = d = 0 e também não roda. Os dois casos de borda saem de graça da condição e < d.

O mesmo par de índices decide palíndromo sem fatiar nada:

def eh_palindromo(s):
    e, d = 0, len(s) - 1
    while e < d:
        if s[e] != s[d]:
            return False       # divergiu, já era
        e += 1
        d -= 1
    return True

Repare no que ficou de fora: nenhum s[::-1], nenhum s[e:d], nenhuma alocação. Cada comparação lê memória que já existe. Escrever s == s[::-1] dá a mesma resposta e aloca uma string inteira para isso. É o Two Pointers aplicado a texto, e é por isso que os dois tópicos andam colados.

Esta é a tabela que junta tudo. Ela compara o que um array de caracteres faz e o que uma string imutável faz:

Repare na linha de comparação: comparar duas strings não é O(1). Ela para na primeira divergência, o que costuma ser rápido, mas o pior caso percorre tudo. Isso importa mais do que parece no problema da próxima seção.

Rotate String: da força bruta ao truque de uma linha

O LeetCode 796 existe para castigar exatamente o hábito de concatenar em laço. Um shift pega o caractere mais à esquerda e joga para a direita: abcde vira bcdea. Dado s e goal, responda se dá para chegar em goal fazendo shifts em s.

A primeira solução que vem à cabeça é rotacionar e comparar, até dar a volta completa:

def rotate_string(s, goal):
    if len(s) != len(goal):
        return False
    for _ in range(len(s)):
        s = s[1:] + s[0]      # DUAS strings novas por volta
        if s == goal:
            return True
    return False

Aquele s[1:] já é uma string nova com n-1 caracteres copiados, e a concatenação aloca mais uma, de n. São 2n - 1 cópias por rotação e até n rotações: n(2n - 1) cópias no pior caso, que é O(n²).

A primeira melhora, antes de lembrar do truque, é aplicar o que a seção anterior ensinou: pare de materializar a string em toda volta. Gire na lista de caracteres e só monte a string na hora de comparar.

def rotate_string(s, goal):
    if len(s) != len(goal):
        return False
    chars = list(s)                   # UMA conversão, no começo
    for _ in range(len(s)):
        chars.append(chars.pop(0))    # o shift, sem criar string
        if "".join(chars) == goal:    # só aqui materializa
            return True
    return False

Continua O(n²), e vale entender por quê: o join custa O(n) por volta, a comparação custa O(n) por volta, e até o pop(0) custa O(n), porque desloca a lista inteira uma casa para a esquerda. O que muda é a pressão de memória: uma string nova por rotação em vez de duas, e o shift virou movimentação de ponteiros dentro de um buffer que já existe. É a versão que já ganha muito numa entrevista, porque mostra que você enxergou a alocação.

O truque é perceber que todas as rotações de s já moram dentro de s + s. Com abcde, o dobrado é abcdeabcde, e ali dentro estão abcde, bcdea, cdeab, deabc e eabcd, cada uma começando numa posição:

def rotate_string(s, goal):
    return len(s) == len(goal) and goal in s + s

Uma concatenação (2n cópias, uma string nova) e uma busca de substring. Rode os dois modos no visualizador e compare os cartões: com n = 5, o laço chega a 45 cópias no pior caso, o truque gasta 10, sempre.

Comece pelo preset caso feliz (abcde para cdeab) no modo laço: ele acha na segunda rotação, com 18 caracteres copiados e 4 strings novas. Troque para o modo truque e veja a janela do goal deslizando sobre o dobrado sem alocar mais nada. Depois rode o preset não rotaciona, que é o pior caso, e compare os contadores no fim.

O que o in esconde

Já que a solução de uma linha terceiriza o trabalho todo para a busca de substring, vale abrir essa caixa. Ela é um problema por si só, o Find the Index of the First Occurrence, e a versão ingênua tenta cada ponto de partida e compara para a frente:

def indice_de(texto, alvo):
    n, m = len(texto), len(alvo)
    if m == 0:
        return 0                            # alvo vazio casa no começo
    for i in range(n - m + 1):              # até onde o alvo ainda cabe
        j = 0
        while j < m and texto[i + j] == alvo[j]:
            j += 1
        if j == m:
            return i                        # casou inteiro
    return -1

São até n - m + 1 pontos de partida e até m comparações em cada um: O(n · m) no pior caso. Esse pior caso não é teórico, ele aparece com texto = "aaaaaaaaab" e alvo = "aaab", onde quase toda tentativa vai quase até o fim antes de falhar. Repare no range(n - m + 1): começar depois disso é perder tempo, porque o alvo não cabe mais, e é aí que mora o off-by-one mais comum do problema.

KMP e rolling hash existem justamente para derrubar isso para O(n + m), reaproveitando o que a tentativa anterior já provou em vez de recomeçar do zero. É a mesma ideia da Sliding Window: não recalcular o que já foi calculado.

E fica o recado honesto: o truque do s + s é bem característico deste problema, difícil de inventar do zero na hora. Numa entrevista, a versão com a lista de caracteres, que já mostra preocupação com alocação, e o teste de tamanho no começo, que descarta o caso impossível de graça, já contam muito a seu favor.

Uma curiosidade: esse deslocamento circular do alfabeto é a cifra de César, a primeira criptografia registrada, que empurrava cada letra três casas para a direita. Ela funcionava não por ser forte, mas porque quase ninguém sabia ler e ninguém tinha máquina para testar os 25 deslocamentos possíveis. Hoje o seu laço testa todos eles em microssegundos, e é exatamente isso que este problema pede.

As armadilhas que pegam todo mundo

Fatiar copia. s[1:], substring, split, strip, upper, replace: todos devolvem uma string nova em O(n). Encadear cinco desses é cinco passadas e cinco alocações. Dentro de um laço, é O(n²) disfarçado de código limpo.

Não confie na sorte do interpretador. Se você cronometrar o laço de concatenação no CPython, pode se surpreender com um resultado bom demais: existem casos em que ele aumenta o buffer no lugar, em vez de copiar, quando a string tem uma referência só. É uma gentileza da implementação, não uma garantia da linguagem. Basta uma segunda referência para a mesma string, outra implementação de Python ou outra linguagem para o O(n²) voltar. O join não depende de sorte.

Comparar não é uma operação. a == b é O(n). Comparar dentro de um laço que também é O(n) dá O(n²), mesmo sem nenhuma concatenação à vista.

Assumir ASCII. O código funciona na sua máquina, com nomes em inglês, e quebra com João, com chinês tradicional ou com um emoji no campo de nome. Misturar bytes de encodings diferentes é como concatenar dois arrays com tipos diferentes: o tamanho até fecha, o conteúdo vira lixo. É o caso real de uma integração com uma transportadora de Taiwan em que tudo chega em chinês tradicional: se você trata os bytes como se fossem do seu encoding, o texto sai embaralhado e o bug só aparece em produção.

á pode não ser igual a á. O Unicode deixa escrever o mesmo caractere de dois jeitos: um code point só (á = U+00E1, a forma NFC) ou a letra mais um acento combinante (a + U+0301, a forma NFD). Os dois desenham exatamente a mesma coisa na tela, e == diz que são diferentes, porque compara code point a code point. Antes de comparar, ordenar, deduplicar ou usar texto como chave, normalize: unicodedata.normalize("NFC", s) no Python, s.Normalize() no C#, s.normalize("NFC") no JavaScript. É o bug clássico de um nome digitado no macOS não bater com o mesmo nome vindo do Windows.

Alocar demais é caro mesmo com coletor de lixo. Ter um garbage collector não é licença para produzir lixo. Objeto de vida curta é barato de coletar, porque morre na geração mais nova, mas volume alto de alocação força coletas frequentes, e coleta frequente é a sua aplicação parando para respirar. Pior: a string que sobrevive a algumas coletas é promovida para uma geração mais velha, e essas são justamente as caras de limpar. Cada resposta JSON que você monta é manipulação de string, e o efeito acumula.

Otimizar onde não dói. Se a string tem 20 caracteres e a função roda uma vez por requisição, escolha o código mais legível. O Big O só cobra a conta quando a escala aparece, e o gargalo real pode estar no banco ou na rede. Continue medindo antes de reescrever, como no tópico de Big O.

Achar que só existe um "tamanho". Bytes, code points, unidades UTF-16 e grafemas são quatro números diferentes para a mesma string. Antes de validar um limite de tamanho, decida qual deles é o certo para o seu caso.

Como praticar isto

Antes de rodar cada visualizador, preveja o número e só depois confira. É aí que o aprendizado acontece.

No visualizador de montagem: clique no atalho CCC (3 letras) e diga, antes de rodar, quantas cópias o += vai fazer. São 6 contra 3. Depois clique em CRAFTCODECLUB, de 13 letras: são 91 contra 13. Por fim, entrada vazia: o laço não roda nenhuma vez, nada é alocado, e é justamente esse o caso que quebra implementação apressada.

No visualizador de bytes: digite o seu nome com acento e compare UTF-8 com UTF-16. Depois clique em família, volte o encoding para UTF-8 e explique em voz alta por que 7, 11, 25 e 1 são todos respostas corretas para "qual é o tamanho disso". Termine clicando em ASCII com a família selecionada: os quatro emojis e as três colas viram sete ? e a informação some para sempre.

No visualizador do Rotate String: rode abcde para cdeab nos dois modos e anote os quatro contadores. Depois teste tamanhos diferentes e repare que o teste de uma linha devolve False sem copiar nada. Por fim, rode volta completa (abcd para abcd) e veja o laço achar só na quarta rotação, depois de dar a volta inteira, enquanto o truque acha na posição 0.

Os casos de borda que você tem que testar antes de submeter

Passe esta lista em qualquer problema de string, sempre na mesma ordem. É mais rápido do que ler a mensagem de erro do juiz online:

O que cada problema da lista cobra

A lista de problemas logo abaixo está na ordem de resolver, do mais direto ao mais difícil. Antes de abrir cada um, tenha claro qual peça desta página ele exercita:

• Reverse String: os dois índices trocando no array de caracteres, com O(1) de espaço extra. Se você usar s[::-1] ou reversed(), resolveu o exercício e perdeu a aula.
• Valid Anagram: o contador de frequência da primeira seção. Resolva com o array de 26 e depois responda: o que muda se a entrada puder ter acento ou emoji?
• Rotate String: o problema desta página. Escreva as três versões (laço ingênuo, lista de caracteres, goal in s + s) e compare os contadores no visualizador acima antes de olhar o editorial.
• Find the Index of the First Occurrence: implemente a busca ingênua na mão, com o range(n - m + 1) certo, em vez de chamar find. É o pré-requisito para entender KMP depois.
• Zigzag Conversion: o padrão de k builders da seção do builder, mais o k == 1 que quase todo mundo esquece.
• Longest Palindromic Substring: junta tudo. A saída ingênua é gerar todas as substrings e testar cada uma, O(n³). O caminho bom é expandir a partir do centro: cada posição é um centro em potencial, e você abre para os dois lados enquanto os caracteres baterem.

def maior_palindromo(s):
    if not s:
        return ""
    ini, fim = 0, 0
    for centro in range(len(s)):
        # dois centros por posição: ímpar ("aba") e par ("abba")
        for e, d in ((centro, centro), (centro, centro + 1)):
            while e >= 0 and d < len(s) and s[e] == s[d]:
                e -= 1
                d += 1
            e, d = e + 1, d - 1      # o laço passou um do fim, volta um
            if d - e > fim - ini:
                ini, fim = e, d
    return s[ini:fim + 1]            # UMA fatia, no fim de tudo

São 2n centros e até n/2 passos em cada um: O(n²) em tempo e O(1) em espaço extra. Repare que ele guarda índices, não substrings, e só materializa a resposta na última linha. A versão que faz melhor = s[e:d+1] dentro do laço fatia O(n) a cada melhora e volta a alocar sem precisar, que é a armadilha desta página inteira aparecendo mais uma vez.

Daqui, o caminho natural é Two Pointers, que resolve palíndromo e inversão com dois índices convergindo, e Sliding Window, que domina os problemas de substring com janela variável. Se a dúvida for de vocabulário, entre "substring" e "subsequence", passe antes pelos 4 "sub".

Vídeo da aula

Direto do canal da comunidade Craft & Code Club · 1:45:57.

▶

Problemas para praticar

Na ordem em que recomendamos resolver. Marque os que você já fez, fica salvo aqui.

Referências

Artigos e materiais externos para se aprofundar.

Este tópico também tem página própria, fora deste roadmap: Strings.