24 de Março
Maior substring palindrômica
Como perceber que todo palindromo tem um centro e usar isso para evitar uma solução de programacao dinamica mais pesada do que o necessário.
Strings e Expansao Intermediario 22 min TypeScript
Dada uma string s, retorne a maior substring palindromica.
Aqui no SeniorPath, se houver empate no tamanho, retorne a que aparece primeiro na string.
Exemplo:
Input: s = "babad"
Output: "bab"
O que perceber antes de codar
- Palindromo em substring continua sendo comparação espelhada.
- O centro pode ser uma letra só ou o espaco entre duas letras.
- Aqui a comparação precisa de desempate deterministico quando ha mais de uma resposta valida.
Erros comuns
- considerar apenas centros impares e perder casos como `"bb"`
- ir direto para DP 2D sem verificar a abordagem mais simples
Passo 1 - Separar substring de subsequencia
O problema pede substring.
Isso significa:
- os caracteres precisam estar contiguos
Entao não vale pular letras no meio.
Passo 2 - Escrever a versão inicial mais direta
A versão inicial natural e:
- testar toda substring possível
- checar se ela e palindromo
- guardar a maior
Funciona.
Mas vira muito trabalho repetido.
Passo 3 - Perguntar o que todo palindromo tem em comum
Todo palindromo cresce a partir de um centro.
Esse centro pode ser:
- uma unica letra, como em
"aba" - o espaco entre duas letras, como em
"abba"
Se você souber expandir desse centro para fora, não precisa enumerar tudo do zero.
Passo 4 - Transformar isso em expansao com dois ponteiros
Para cada posição da string:
- tente centro impar:
(i, i) - tente centro par:
(i, i + 1)
Enquanto os dois lados forem iguais, continue expandindo.
O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.
Codigo inicial
export function longestPalindrome(s: string): string {
// sua solução aqui
return ""
}
Ainda não resolveu?
Ver a solução agora pode reduzir o aprendizado. Vale a pena tentar mais um pouco.
Abrir a solucao de referencia
Sem JavaScript, a solucao de referencia aparece inline em vez de um dialogo.
Solução
Complexidade final
Tempo: O(n^2)
Espaço: O(1)
Solução 1 - Testar toda substring O(n²)
Boa versão inicial para deixar claro de onde vem o custo alto.
function isPalindrome(candidate: string): boolean {
let left = 0
let right = candidate.length - 1
while (left < right) {
if (candidate[left] !== candidate[right]) {
return false
}
left += 1
right -= 1
}
return true
}
export function longestPalindrome(s: string): string {
let best = s[0] ?? ""
for (let start = 0; start < s.length; start += 1) {
for (let end = start; end < s.length; end += 1) {
const candidate = s.slice(start, end + 1)
if (candidate.length > best.length && isPalindrome(candidate)) {
best = candidate
}
}
}
return best
}Funciona, mas compara substring demais.
Solução 2 - Expandir do centro com dois ponteiros
Agora você usa a estrutura do palindromo em vez de tentar tudo no escuro.
function expandAroundCenter(s: string, left: number, right: number): [number, number] {
while (left >= 0 && right < s.length && s[left] === s[right]) {
left -= 1
right += 1
}
return [left + 1, right - 1]
}
export function longestPalindrome(s: string): string {
if (s.length <= 1) {
return s
}
let bestStart = 0
let bestEnd = 0
for (let index = 0; index < s.length; index += 1) {
const odd = expandAroundCenter(s, index, index)
const even = expandAroundCenter(s, index, index + 1)
for (const [start, end] of [odd, even]) {
const candidateLength = end - start + 1
const bestLength = bestEnd - bestStart + 1
if (candidateLength > bestLength || (candidateLength === bestLength && start < bestStart)) {
bestStart = start
bestEnd = end
}
}
}
return s.slice(bestStart, bestEnd + 1)
}O insight forte aqui e escolher a propriedade certa: palindromos não precisam de tabela 2D para existir. Eles só precisam de um centro.
O que dizer na entrevista
Uma explicação curta e boa seria:
A versão inicial testa toda substring e verifica se ela e palindromo, o que custa caro demais. A versão forte usa o fato de que todo palindromo tem um centro. Para cada indice eu expando em volta dele com dois ponteiros, tanto no caso impar quanto no par, e atualizo a melhor resposta.
Isso mostra que você:
- entendeu a estrutura do problema
- escolheu a abordagem simples antes da pesada
- explica o motivo da otimização, não só o código
Quando esse padrão aparece de novo
Esse padrão reaparece quando você precisa:
- comparar espelhos em volta de um ponto
- trabalhar com strings contiguas
- preferir uma solução estrutural a uma
programacao dinamicamais pesada
O ponto não e decorar “expande do centro”.
O ponto e perceber quando o centro e a propriedade mais útil da string.