Maior subsequência e substring palindrômicas
Aplique DP de intervalos para encontrar a maior subsequência palindrômica e o truque de expansão ao redor do centro para encontrar a maior substring palindrômica.
Maior subsequência e substring palindrômicas é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 2 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
Definições de palíndromos revisitadas
Uma subsequência palindrômica é uma subsequência (cujos elementos não precisam ser contíguos) que pode ser lida da mesma forma para a frente e para trás. Uma substring palindrômica exige caracteres contíguos. Para 'bbbab', a maior subsequência palindrômica é 'bbbb' (comprimento 4), enquanto a maior substring palindrômica é 'bbb' (comprimento 3). Esses dois problemas exigem técnicas diferentes, apesar dos nomes semelhantes.
Maior subsequência palindrômica: estado LPS
Defina dp[i][j] como o comprimento da maior subsequência palindrômica em s[i..j]. A recorrência é: se s[i] == s[j], então dp[i][j] = dp[i+1][j-1] + 2 (os dois caracteres iguais estendem o palíndromo interno). Caso contrário, dp[i][j] = max(dp[i+1][j], dp[i][j-1]) (ignore o caractere esquerdo ou direito). Caso-base: dp[i][i] = 1 para todos os caracteres únicos.
s = 'bbbab'
n = len(s)
dp = [[0]*n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
print('Base cases set, dp[i][i] = 1 for all i')Ordem de preenchimento e implementação de LPS
Preenchemos a tabela LPS em ordem crescente do comprimento dos intervalos, seguindo o mesmo padrão da programação dinâmica por intervalos geral. Para cada intervalo [i, j] de comprimento 2 ou maior, verificamos se os dois caracteres das extremidades são iguais e aplicamos a recorrência. A resposta final é dp[0][n-1], a LPS da string inteira.
def longest_palindromic_subsequence(s):
n = len(s)
dp = [[0]*n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
for length in range(2, n+1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j]:
inner = dp[i+1][j-1] if length > 2 else 0
dp[i][j] = inner + 2
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
return dp[0][n-1]
print(longest_palindromic_subsequence('bbbab')) # 4Equivalência entre LPS e LCS
Uma alternativa elegante: a LPS da string s é igual à LCS de s e de sua inversa s[::-1]. Isso ocorre porque qualquer subsequência palindrômica de s é uma subsequência comum de s e de sua inversa. Essa redução permite reutilizar diretamente seu código de LCS. Para 'bbbab', a string invertida é 'babbb', e a LCS delas tem comprimento 4.
def lps_via_lcs(s):
t = s[::-1]
m, n = len(s), len(t)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if s[i-1] == t[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
print(lps_via_lcs('bbbab')) # 4Maior substring palindrômica: força bruta
A maior substring palindrômica exige caracteres contíguos. Uma abordagem de força bruta verifica todas as substrings O(n²) e valida cada uma em tempo O(n), totalizando O(n³). Existem duas abordagens mais rápidas: programação dinâmica por intervalos em tempo e espaço O(n²) e expansão ao redor do centro em tempo O(n²), mas espaço O(1). Em entrevistas, a expansão ao redor do centro é preferida porque tem uma constante menor e um código mais limpo.
Programação dinâmica por intervalos para substrings palindrômicas
Defina dp[i][j] = True se s[i..j] for um palíndromo. Recorrência: dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]. Casos-base: dp[i][i] = True e dp[i][i+1] = (s[i] == s[i+1]). Acompanhe o palíndromo de maior comprimento encontrado. Preencha em ordem crescente de comprimento. Isso executa em tempo O(n²) e espaço O(n²).
def longest_palindrome_dp(s):
n = len(s)
dp = [[False]*n for _ in range(n)]
start, max_len = 0, 1
for i in range(n):
dp[i][i] = True
for i in range(n-1):
if s[i] == s[i+1]:
dp[i][i+1] = True
start, max_len = i, 2
for length in range(3, n+1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j] and dp[i+1][j-1]:
dp[i][j] = True
if length > max_len:
start, max_len = i, length
return s[start:start+max_len]
print(longest_palindrome_dp('babad')) # 'bab' or 'aba'Técnica de expansão ao redor do centro
A abordagem de expansão ao redor do centro considera cada caractere (e cada par de caracteres adjacentes) como um possível centro de palíndromo e se expande para fora enquanto os dois lados forem iguais. Existem 2n-1 centros possíveis (n de comprimento ímpar e n-1 de comprimento par). Cada expansão leva no máximo tempo O(n), resultando em O(n²) no total, com espaço O(1) — desempenho ideal para a maioria das situações de entrevista.
def longest_palindrome_expand(s):
def expand(l, r):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1
r += 1
return r - l - 1 # length of palindrome
start, max_len = 0, 1
for i in range(len(s)):
odd = expand(i, i) # odd-length
even = expand(i, i+1) # even-length
best = max(odd, even)
if best > max_len:
max_len = best
start = i - (best - 1) // 2
return s[start:start+max_len]
print(longest_palindrome_expand('cbbd')) # 'bb'Otimização de espaço da LPS
A programação dinâmica por intervalos para LPS usa espaço O(n²). Quando você precisa apenas do comprimento (e não da subsequência real), pode reduzir o espaço observando que dp[i][j] depende apenas de dp[i+1][j-1], dp[i+1][j] e dp[i][j-1]. Reutilizando linhas e armazenando um valor da diagonal, é possível obter espaço O(n) — embora a implementação seja mais complexa e raramente seja necessária em entrevistas.
Reconstrução da LPS
Para reconstruir a subsequência palindrômica real, rastreie a tabela de programação dinâmica de trás para a frente. Comece em (0, n-1). Se s[i] == s[j], adicione esse caractere às duas extremidades do resultado e avance para (i+1, j-1). Caso contrário, avance para aquele entre (i+1, j) e (i, j-1) que tiver o maior valor. Esse rastreamento guloso recupera de forma única uma subsequência palindrômica ideal.
def reconstruct_lps(s, dp):
result = []
i, j = 0, len(s) - 1
while i < j:
if s[i] == s[j]:
result.append(s[i])
i += 1; j -= 1
elif dp[i+1][j] > dp[i][j-1]:
i += 1
else:
j -= 1
# middle character for odd-length
mid = [s[i]] if i == j else []
return ''.join(result + mid + result[::-1])
print('Traceback recovers one optimal LPS')Comparação da complexidade de tempo entre LPS e LCS
Tanto a LPS por programação dinâmica de intervalos quanto a LCS executam em tempo O(n²) e espaço O(n²). A expansão ao redor do centro para a maior substring palindrômica usa tempo O(n²), mas apenas espaço O(1). O algoritmo de Manacher resolve o problema da substring em tempo e espaço O(n), mas é complexo o suficiente para que os entrevistadores raramente o esperem. Na maioria dos contextos de entrevista, a expansão ao redor do centro é a solução ideal esperada para a variante de substring.
Armadilhas comuns e casos extremos
Tenha cuidado com estas armadilhas: (1) confundir subsequência com subcadeia — são problemas diferentes, com soluções diferentes; (2) o caso base do DP de intervalos para intervalos de comprimento 2 requer um tratamento especial, pois dp[i+1][j-1] seria dp[i+1][i] (intervalo vazio); (3) para a expansão ao redor do centro, inicialize max_len = 1 (cada caractere isolado é um palíndromo); e (4) ao extrair o resultado, calcule start = i - (best-1)//2 para encontrar corretamente o índice inicial a partir do centro.
Verificação rápida
Teste sua compreensão dos conceitos de Estruturas de Dados e & Algoritmos — Preparação para Entrevistas de Programação apresentados nesta lição.
Recapitulação da lição
Nesta lição, você aprendeu: LPS usa DP de intervalos com a recorrência dp[i][j] = dp[i+1][j-1]+2 quando os caracteres coincidem, a subcadeia palindrômica mais longa é resolvida da melhor forma com expansão ao redor do centro, em tempo O(n²) e espaço O(1), e LPS é igual ao LCS da cadeia de caracteres e de sua reversa. A seguir, abordaremos o particionamento de palíndromos II, que combina uma tabela de palíndromos com DP unidimensional para obter o número mínimo de cortes.
Perguntas Frequentes
A aula “Maior subsequência e substring palindrômicas” é grátis?
Sim — o texto completo de “Maior subsequência e substring palindrômicas” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “Maior subsequência e substring palindrômicas”?
Aplique DP de intervalos para encontrar a maior subsequência palindrômica e o truque de expansão ao redor do centro para encontrar a maior substring palindrômica. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 2 de 4.
Quanto tempo leva a aula “Maior subsequência e substring palindrômicas”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Padrão de DP de intervalos e ordem de preenchimento
- Maior subsequência e substring palindrômicas
- Particionamento de palíndromos II
- Balões estourados: DP de intervalos reversa