Síntese: qual padrão usar?
Cinco padrões cobertos. Hora de treinar o reflexo que vale a entrevista: ler um enunciado de string novo e saber qual ferramenta sacar — com justificativa.
A árvore de decisão da seção
1. A ORDEM dos caracteres NÃO importa, só a composição?
├── Comparar/agrupar strings inteiras por composição
│ → CONTAGEM DE FREQUÊNCIA (anagramas)
└── Continue ↓
2. A resposta é uma SUBSTRING contígua que cresce/encolhe sob uma condição?
→ SLIDING WINDOW com mapa de frequência
(sem repetição / ≤ k trocas / cobre um alvo)
3. O problema é sobre SIMETRIA (palíndromo)?
├── "Isto é um palíndromo?" → TWO POINTERS convergentes
└── "Quantos / qual o maior?" → EXPANDIR DO CENTRO (ímpar e par)
4. Há ANINHAMENTO ou casamento de aberturas/fechamentos? Ou "último pendente"?
→ PILHA (LIFO)
5. Preciso REPRESENTAR dados em string e recuperá-los sem ambiguidade?
→ CODIFICAÇÃO length-prefix (design)
E o teste de sanidade de sempre: os limites. Lembre que enumerar todas as substrings já é O(n²) — se n é grande, quase nunca é esse o caminho.
O mapa completo da seção
| Padrão | Pergunta-chave | Estrutura | Tempo | Espaço |
|---|---|---|---|---|
| Frequência (anagramas) | "mesma composição?" | mapa de contagens | O(n) ou O(n·k log k) | O(1)* |
| Sliding window | "substring que satisfaz X?" | janela + mapa | O(n) | O(1)* |
| Two pointers | "é palíndromo?" | dois índices das pontas | O(n) | O(1) |
| Expandir do centro | "quantos/maior palíndromo?" | dois índices do centro | O(n²) | O(1) |
| Pilha | "aninhamento / último pendente?" | stack LIFO | O(n) | O(n) |
| Codificação | "representar sem ambiguidade?" | length-prefix | O(n) | O(n) |
* O(1) quando o alfabeto é fixo (ex.: 26 letras); senão O(min(n, alfabeto)).
E a conexão com a seção anterior, que vale internalizar: frequência é o hash map, sliding window e two pointers vieram do Array. Você não aprendeu 5 ferramentas novas — aprendeu a aplicar as do Array a caracteres e ganhou pilha, expandir-do-centro e codificação de presente.
Quiz da seção
Enunciados que você não viu nas aulas. Identifique o padrão e saiba dizer o porquê. 7+ acertos: pronto para a prova.
🧠 Quiz da seção: String
0/81. 'Verifique se s2 contém alguma permutação de s1 como substring.' Qual padrão?
2. 'Dada uma string, qual o tamanho da maior substring com no máximo 2 caracteres distintos?' Qual padrão?
3. 'Quantas substrings palindrômicas existem em s?' Qual padrão e qual a complexidade?
4. 'Remova todos os parênteses inválidos para tornar a expressão válida.' Que estrutura é a base natural?
5. 'É um palíndromo se você puder remover no máximo um caractere?' Qual padrão?
6. 'Codifique uma árvore binária em string e reconstrua.' Qual princípio da seção String se aplica?
7. 's e t são anagramas?' — por que NÃO usar sliding window aqui?
8. Qual a ideia-mãe que liga a seção String à seção Array?
Pronto para a prova?
A prova final da seção String tem três problemas inéditos — fácil, médio e difícil — com casos ocultos. As cinco aulas cobrem tudo que você precisa, e a árvore de decisão acima resolve a escolha do padrão dos três.
Boa prova! Volte para a página da seção e clique em "Prova final".