Reconhecendo problemas de string
Boa notícia: você já sabe metade desta seção. Uma string é um array de caracteres — então two pointers, sliding window e hash map (que você dominou na seção Array) reaparecem aqui. Esta seção adiciona o que é genuinamente novo das strings.
Como na seção Array, cada aula de padrão abre com um 🎯 Tente primeiro: resolva antes de ver a teoria. Sentir a dificuldade é o que faz a ideia encaixar.
String é um array de caracteres
"abc" é, na prática, ['a', 'b', 'c'] com índices 0, 1, 2. Acessar
s[i] é O(1), percorrer a string é O(n), e os padrões de array funcionam
quase iguais. Por isso String vem logo depois de Array no curso: é o lugar
perfeito para consolidar aqueles padrões num contexto novo antes de partir
para estruturas mais complexas.
Há só uma diferença técnica que vale registrar agora: em muitas linguagens (incluindo Python e JavaScript) strings são imutáveis. Você não troca um caractere no lugar — cria uma string nova. Montar uma string concatenando dentro de um loop pode esconder um custo O(n²); quando precisar construir uma saída grande, acumule numa lista e junte no final.
O que se reaproveita do Array
| Padrão do Array | Como aparece em String |
|---|---|
| Hash map ("já vi?") | contagem de caracteres — a assinatura de frequência |
| Sliding window | substring que cresce/encolhe, com um mapa de contagens como estado |
| Two pointers | varrer a string das duas pontas (palíndromos) |
O que é novo nesta seção
| Ferramenta nova | Para quê |
|---|---|
| Mapa de frequência | identidade de uma string ignorando a ordem (anagramas) |
| Expandir do centro | achar palíndromos crescendo a partir de cada centro |
| Pilha | casar aberturas/fechamentos, resolver o "mais aninhado" primeiro |
| Codificação | serializar dados em texto sem ambiguidade |
O método continua o mesmo
O roteiro da seção Array vale igualzinho aqui: resolver no braço → força bruta → achar o desperdício → conferir os limites. Só muda o repertório de padrões que você considera no passo do desperdício.
Um detalhe específico de strings vale ouro no passo "força bruta": gerar todas as substrings de uma string custa O(n²) (há n² delas), e avaliar cada uma pode somar mais um fator. Boa parte desta seção é justamente sobre não cair nesse O(n²)/O(n³) ingênuo.
Os 10 problemas da seção
Usaremos estes problemas do Top 75 como exemplos dos padrões:
- Valid Anagram e Group Anagrams → contagem de caracteres
- Longest Substring Without Repeating, Longest Repeating Character Replacement, Minimum Window Substring → sliding window com frequência
- Valid Palindrome, Longest Palindromic Substring, Palindromic Substrings → two pointers e expandir do centro
- Valid Parentheses → pilha
- Encode and Decode Strings → codificação / design
🧠 Quiz de fixação
0/31. Por que os padrões da seção Array (two pointers, sliding window, hash map) reaparecem em String?
2. Gerar e avaliar todas as substrings de uma string de tamanho n custa, no mínimo:
3. Por que concatenar caracteres numa string dentro de um loop pode ser uma armadilha de desempenho?
Resumo
- String é array de caracteres: índices, acesso O(1), e os padrões de array valem aqui.
- Novidades da seção: contagem de frequência, expandir do centro, pilha, codificação.
- Cuidado com o O(n²) das "todas as substrings" e com o O(n²) escondido da concatenação em loop.
Próxima aula: a ferramenta que dá a uma string sua identidade sem ordem — a contagem de caracteres, e os anagramas.