Maior Subsequência Comum
Defina a recorrência de LCS para duas strings, preencha a tabela 2D e reconstrua a subsequência real percorrendo a tabela de trás para frente.
Maior Subsequência Comum é uma aula grátis de DSA 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 DSA Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de DSA Interview Prep inclui 4 aulas no total.
O que é uma Subsequência?
Uma subsequência de uma cadeia de caracteres é formada pela remoção de alguns caracteres (ou de nenhum), sem alterar a ordem dos caracteres restantes. Por exemplo, 'ACE' é uma subsequência de 'ABCDE', mas 'AEC' não é (a ordem foi violada). A Maior Subsequência Comum (LCS) de duas cadeias é a subsequência mais longa que aparece em ambas. 'ABCBDAB' e 'BDCABA' compartilham a LCS 'BCBA' ou 'BDAB', de comprimento 4.
# Subsequence vs Substring
# 'ACE' is a subsequence of 'ABCDE' (skip B, D)
# 'ACE' is NOT a substring of 'ABCDE' (must be contiguous)
# LCS examples:
# LCS('ABCBDAB', 'BDCABA') = 4 ('BCBA' or 'BDAB')
# LCS('AGGTAB', 'GXTXAYB') = 4 ('GTAB')
# LCS('ABC', 'AC') = 2 ('AC')
print('Subsequence check: ACE in ABCDE')
text = 'ABCDE'
pattern = 'ACE'
i = 0
for ch in text:
if i < len(pattern) and ch == pattern[i]: i += 1
print('Found:', i == len(pattern)) # TrueDerivação da Recorrência de LCS
Defina dp[i][j] = comprimento da LCS de text1[:i] e text2[:j]. Se os caracteres coincidirem (text1[i-1] == text2[j-1]), estendemos a LCS em 1: dp[i][j] = dp[i-1][j-1] + 1. Se não coincidirem, escolhemos a melhor opção entre ignorar um caractere de cada cadeia: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Caso base: dp[0][j] = dp[i][0] = 0 (a LCS com uma cadeia vazia tem comprimento 0).
def lcs_length(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1 # extend match
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) # skip one
return dp[m][n]
print(lcs_length('ABCBDAB', 'BDCABA')) # 4
print(lcs_length('AGGTAB', 'GXTXAYB')) # 4
print(lcs_length('ABC', 'AC')) # 2Rastreando a Tabela de LCS
Para text1='ABCD' e text2='ACBD': comece com todos os valores iguais a zero. Quando os caracteres coincidirem (A-A, C-C, B-B se estiverem na posição correta, D-D), dp[i][j] = dp[i-1][j-1] + 1. Caso contrário, escolha o máximo entre os vizinhos à esquerda e acima. Percorrer a tabela preenchida mostra como os passos diagonais correspondem aos caracteres coincidentes. O valor final dp[4][4] fornece o comprimento da LCS.
def lcs_trace(text1, text2):
m, n = len(text1), len(text2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
# Print table
print(' ', ' '.join(text2))
for i, row in enumerate(dp):
label = ' ' if i == 0 else text1[i-1]
print(label, row)
return dp[m][n]
lcs_trace('ABCD', 'ACBD')Reconstrução da LCS real
Para recuperar a cadeia LCS real, percorra a tabela de DP em sentido inverso a partir de dp[m][n]. Se text1[i-1] == text2[j-1], esse caractere faz parte da LCS — registre-o e mova-se diagonalmente para (i-1, j-1). Se dp[i-1][j] > dp[i][j-1], mova-se para cima; caso contrário, mova-se para a esquerda. Inverta os caracteres coletados ao final, pois o percurso foi feito em sentido inverso. Essa reconstrução é executada em tempo O(m+n).
def lcs_reconstruct(text1, text2):
m, n = len(text1), len(text2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
# Backtrack
result = []
i, j = m, n
while i > 0 and j > 0:
if text1[i-1] == text2[j-1]:
result.append(text1[i-1])
i -= 1; j -= 1
elif dp[i-1][j] > dp[i][j-1]:
i -= 1
else:
j -= 1
return ''.join(reversed(result))
print(lcs_reconstruct('ABCBDAB', 'BDCABA')) # BCBA or BDABOtimização de espaço para O(n)
A tabela da LCS precisa apenas da linha atual e da linha anterior. Você pode usar um vetor unidimensional de tamanho n+1 e uma variável diagonal para armazenar o valor que estava em dp[i-1][j-1] antes de ser sobrescrito. Percorra cada linha da esquerda para a direita. Após cada célula, o dp[j] atualizado contém o valor da linha atual, e você salva o valor anterior em diagonal antes de sobrescrevê-lo.
def lcs_o1_space(text1, text2):
m, n = len(text1), len(text2)
dp = [0] * (n + 1) # represents previous row
for i in range(1, m + 1):
diag = 0 # dp[i-1][j-1]
for j in range(1, n + 1):
temp = dp[j] # save current (will become diagonal for next j)
if text1[i-1] == text2[j-1]:
dp[j] = diag + 1
else:
dp[j] = max(dp[j], dp[j-1])
diag = temp
return dp[n]
print(lcs_o1_space('ABCBDAB', 'BDCABA')) # 4
print(lcs_o1_space('AGGTAB', 'GXTXAYB')) # 4Relação entre LCS e distância de edição
A LCS está intimamente relacionada à distância de edição (distância de Levenshtein). Se você conhece a LCS, pode calcular a distância mínima de edição usando apenas inserções e exclusões: edit_dist = m + n - 2 * LCS(s1, s2). Cada caractere de s1 que não está na LCS precisa ser excluído, e cada caractere de s2 que não está na LCS precisa ser inserido. A substituição não é contabilizada aqui, pois permitimos apenas inserções e exclusões, mas essa fórmula é útil para problemas relacionados.
def lcs_length(s1, s2):
m, n = len(s1), len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if s1[i-1] == s2[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]
def min_edits_insert_delete(s1, s2):
lcs = lcs_length(s1, s2)
return len(s1) + len(s2) - 2 * lcs
print(min_edits_insert_delete('ABCD', 'ANCD')) # 2 (delete B, insert N)
print(min_edits_insert_delete('horse', 'ros')) # 5Operação de exclusão para duas cadeias
Operação de exclusão para duas cadeias (LeetCode 583) pede o número mínimo de exclusões necessárias para tornar duas cadeias iguais. Os caracteres mantidos precisam formar uma subsequência comum, portanto você deve maximizar a LCS e excluir todo o restante. Resposta: m + n - 2 * LCS(s1, s2). Isso equivale à distância de edição com inserções e exclusões apresentada anteriormente. Formular problemas em termos de LCS é uma poderosa técnica de redução.
def min_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
lcs = dp[m][n]
return m + n - 2 * lcs # deletions needed
print(min_distance('sea', 'eat')) # 2 (delete s, delete t)
print(min_distance('leetcode', 'etco')) # 4Maior subcadeia comum
Não confunda LCS (subsequência) com maior subcadeia comum. Uma subcadeia é contígua, portanto, quando os caracteres não coincidem, a contagem é redefinida para 0 em vez de usar o máximo dos vizinhos. A recorrência muda para: se os caracteres coincidirem, dp[i][j] = dp[i-1][j-1] + 1; caso contrário, dp[i][j] = 0. Rastreie o maior valor observado em todas as células.
def longest_common_substring(s1, s2):
m, n = len(s1), len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
max_len = 0
for i in range(1, m+1):
for j in range(1, n+1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
max_len = max(max_len, dp[i][j])
# else dp[i][j] stays 0 (reset)
return max_len
# LCS (subseq) vs substring:
print('LCS subseq:', lcs_length('ABCBDAB', 'BDCABA')) # 4 (BCBA)
print('LCS substring:', longest_common_substring('ABCBDAB', 'BDCABA')) # 2 (BD or AB)LCS para comparação de sequências
A LCS é amplamente usada em ferramentas diff (como o diff do Unix) para comparar arquivos. O roteiro de edição entre dois arquivos é derivado da LCS: as linhas da LCS não são alteradas, as linhas adicionais do arquivo 1 são excluídas e as linhas adicionais do arquivo 2 são inseridas. Entender a LCS ajuda você a compreender como os sistemas de controle de versão acompanham as alterações e por que ocorrem conflitos de mesclagem.
def diff(old_lines, new_lines):
'''Simple diff using LCS to find unchanged lines.'''
m, n = len(old_lines), len(new_lines)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
for j in range(1,n+1):
if old_lines[i-1]==new_lines[j-1]: dp[i][j]=dp[i-1][j-1]+1
else: dp[i][j]=max(dp[i-1][j],dp[i][j-1])
# Backtrack to produce diff
output, i, j = [], m, n
while i>0 or j>0:
if i>0 and j>0 and old_lines[i-1]==new_lines[j-1]:
output.append(' '+old_lines[i-1]); i-=1; j-=1
elif j>0 and (i==0 or dp[i][j-1]>=dp[i-1][j]):
output.append('+ '+new_lines[j-1]); j-=1
else:
output.append('- '+old_lines[i-1]); i-=1
return list(reversed(output))
for line in diff(['a','b','c'], ['a','x','c']): print(line)Menor supersequência comum
A menor supersequência comum (LeetCode 1092) pede a cadeia mais curta que contenha s1 e s2 como subsequências. Cada caractere da LCS aparece uma vez na supersequência; os caracteres que não pertencem à LCS, de ambas as cadeias, precisam ser incluídos. Comprimento = m + n - LCS(s1, s2). Para reconstruí-la, use o mesmo percurso inverso da LCS, mas inclua os caracteres de ambas as cadeias nas posições em que não houver correspondência.
def shortest_common_supersequence(s1, s2):
m, n = len(s1), len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
for j in range(1,n+1):
if s1[i-1]==s2[j-1]: dp[i][j]=dp[i-1][j-1]+1
else: dp[i][j]=max(dp[i-1][j],dp[i][j-1])
# Reconstruct
result, i, j = [], m, n
while i>0 and j>0:
if s1[i-1]==s2[j-1]: result.append(s1[i-1]); i-=1; j-=1
elif dp[i-1][j]>dp[i][j-1]: result.append(s1[i-1]); i-=1
else: result.append(s2[j-1]); j-=1
while i>0: result.append(s1[i-1]); i-=1
while j>0: result.append(s2[j-1]); j-=1
return ''.join(reversed(result))
print(shortest_common_supersequence('abac', 'cab')) # 'cabac' length 5Complexidade da LCS e dicas para entrevistas
O algoritmo clássico da LCS é executado em tempo O(m×n) e espaço O(m×n), reduzível a O(min(m,n)) com a técnica do vetor deslizante. Dicas importantes para entrevistas: (1) Defina claramente o que o estado da DP representa antes de começar a codificar. (2) Trate de forma distinta os casos de correspondência e de não correspondência. (3) Quando pedirem para reconstruir a sequência, descreva o percurso inverso antes de codificá-lo. (4) Mencione a subsequência crescente mais longa (LIS) como um problema relacionado de 1D, solucionável em O(n log n) com ordenação por paciência.
# LCS: O(mn) time, O(min(m,n)) space with rolling array
# Longest Increasing Subsequence (related but 1D):
from bisect import bisect_left
def lis_length(nums):
'''Patience sorting: O(n log n) LIS length.'''
tails = []
for num in nums:
pos = bisect_left(tails, num)
if pos == len(tails): tails.append(num)
else: tails[pos] = num
return len(tails)
print(lis_length([10, 9, 2, 5, 3, 7, 101, 18])) # 4 (2,3,7,101 or 2,5,7,18)Verificação rápida
Teste sua compreensão dos conceitos de Estruturas de Dados & Algoritmos — Preparação para Entrevistas de Programação desta lição.
Resumo da lição
Nesta lição, você aprendeu: a LCS usa dp[i][j] = dp[i-1][j-1]+1 quando há correspondência; caso contrário, usa max(dp[i-1][j], dp[i][j-1]), a sequência real é reconstruída percorrendo diagonalmente as correspondências e seguindo o vizinho maior nas não correspondências, e a LCS fundamenta a distância de edição, as operações de exclusão, a menor supersequência comum e as ferramentas diff. A seguir, vamos deduzir a recorrência da distância de edição (Levenshtein), que adiciona substituições à estrutura da LCS.
Perguntas Frequentes
A aula “Maior Subsequência Comum” é grátis?
Sim — o texto completo de “Maior Subsequência Comum” é 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 DSA Interview Prep, atualize para CoddyKit PRO. O curso de DSA Interview Prep inclui 4 aulas no total.
O que vou aprender em “Maior Subsequência Comum”?
Defina a recorrência de LCS para duas strings, preencha a tabela 2D e reconstrua a subsequência real percorrendo a tabela de trás para frente. Você pratica DSA 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 DSA Interview Prep?
Nenhuma experiência prévia é necessária. DSA 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 Comum”?
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 DSA Interview Prep?
Sim. Cada aula de DSA 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
- Caminhos Únicos e Soma Mínima de Caminho em Grades
- Maior Subsequência Comum
- Distância de Edição (Levenshtein)
- Otimização de Espaço para DP 2D