"""
LCS Problem Statement: Given two sequences, find the length of longest subsequence
present in both of them.  A subsequence is a sequence that appears in the same relative
order, but not necessarily continuous.
Example:"abc", "abg" are subsequences of "abcdefgh".
"""


def longest_common_subsequence(x: str, y: str):
    """
    Finds the longest common subsequence between two strings. Also returns the
    The subsequence found

    Parameters
    ----------

    x: str, one of the strings
    y: str, the other string

    Returns
    -------
    L[m][n]: int, the length of the longest subsequence. Also equal to len(seq)
    Seq: str, the subsequence found

    >>> longest_common_subsequence("programming", "gaming")
    (6, 'gaming')
    >>> longest_common_subsequence("physics", "smartphone")
    (2, 'ph')
    >>> longest_common_subsequence("computer", "food")
    (1, 'o')
    >>> longest_common_subsequence("", "abc")  # One string is empty
    (0, '')
    >>> longest_common_subsequence("abc", "")  # Other string is empty
    (0, '')
    >>> longest_common_subsequence("", "")  # Both strings are empty
    (0, '')
    >>> longest_common_subsequence("abc", "def")  # No common subsequence
    (0, '')
    >>> longest_common_subsequence("abc", "abc")  # Identical strings
    (3, 'abc')
    >>> longest_common_subsequence("a", "a")  # Single character match
    (1, 'a')
    >>> longest_common_subsequence("a", "b")  # Single character no match
    (0, '')
    >>> longest_common_subsequence("abcdef", "ace")  # Interleaved subsequence
    (3, 'ace')
    >>> longest_common_subsequence("ABCD", "ACBD")  # No repeated characters
    (3, 'ABD')
    """
    # find the length of strings

    assert x is not None
    assert y is not None

    m = len(x)
    n = len(y)

    # declaring the array for storing the dp values
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            match = 1 if x[i - 1] == y[j - 1] else 0

            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] + match)

    seq = ""
    i, j = m, n
    while i > 0 and j > 0:
        match = 1 if x[i - 1] == y[j - 1] else 0

        if dp[i][j] == dp[i - 1][j - 1] + match:
            if match == 1:
                seq = x[i - 1] + seq
            i -= 1
            j -= 1
        elif dp[i][j] == dp[i - 1][j]:
            i -= 1
        else:
            j -= 1

    return dp[m][n], seq


if __name__ == "__main__":
    a = "AGGTAB"
    b = "GXTXAYB"
    expected_ln = 4
    expected_subseq = "GTAB"

    ln, subseq = longest_common_subsequence(a, b)
    print("len =", ln, ", sub-sequence =", subseq)
    import doctest

    doctest.testmod()

Declaración de problema

Dadas dos cadenas S y T, busque la longitud de la subsecuencia común más larga (LCS).

Enfoque

Que el dp[i][j] sea la longitud de la subsecuencia común más larga de los prefijos S[1..i] y T[1..j]. Nuestra respuesta (la longitud de LCS) es dp[| S|] [| T|], ya que el prefijo de la longitud de la cadena es la propia cadena.

Tanto dp[0][i] como dp[i][0] son 0 para cualquier i, desde el LCS de prefijo vacío y cualquier otra cosa es una cadena vacía.

Ahora, vamos a tratar de calcular dp[i][j] para cualquier i, j. Digamos S[1..i] = *A y T[1..j] = *B donde * significa cualquier secuencia de letras (podría ser diferente para S y T), A significa cualquier letra y B significa cualquier letra diferente de A. Dado que A != B, nuestro LCS no incluye A o B como último carácter. Así que podríamos tratar de tirar a la distancia el personaje A o B. Si lanzamos A, nuestra longitud LCS será dp[i - 1][j] (ya que tenemos prefijos S[1..i - 1] y T[1..j]). Si intentamos lanzar el carácter B, tendremos prefijos S[1..i] y T[1..j - 1], por lo que la longitud de LCS será dp[i][j - 1]. Mientras buscamos la subsecuencia común más larga, elegiremos el valor máximo de dp[i][j - 1] y dp[i - 1] [j].

¿Pero qué pasa si S[1..i] = *A y T[1..j] = *A? Podríamos decir que el LCS de nuestros prefijos es LCS de prefijos S[1..i - 1] y T[1..j - 1] más la letra A. Así que dp[i][j] = dp[i - 1][j - 1] + 1 es igual a S[i] = T[j].

Pudimos ver que podemos llenar nuestra tabla dp fila por fila, columna por columna. Así que nuestro algoritmo será como:

• Digamos que tenemos cuerdas S de la longitud N y T de la longitud M (numeradas a partir de 1). Vamos a crear la tabla dp de tamaño (N + 1) x (M + 1) numerada a partir de 0.
• Vamos a llenar la 0ª fila y la 0ª columna de dp con 0.
• A continuación, seguimos el algoritmo:

for i in range(1..N):
    for j in range(1..M):
        if(S[i] == T[j])
            dp[i][j] = dp[i - 1][j - 1] + 1
        else
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

Complejidad temporal

O(N * M) - En cualquier caso

Complejidad espacial

O(N * M) - implementación simple O(min {N, M}) - implementación de dos capas (como dp[i][j] depende sólo de las capas i-th e i-th, coudld almacenamos sólo dos capas).

Ejemplo

Digamos que tenemos cuerdas ABCB y BBCB. Construiremos una mesa de este tipo:

# # Una B C B
# 0 0 0 0 0
B 0 ? ? ? ?
B 0 ? ? ? ?
C 0 ? ? ?
B 0 ? ? ? ?

Ahora empezaremos a llenar nuestra mesa desde la 1ª fila. Puesto que S[1] = A y T[1] = B, dp[1] [1] será el valor máximo de dp[0] [1] = 0 y dp[1] [0] = 0. Así que dp[1] [1] = 0. Pero ahora S[2] = B = T[1], así que dp[1] [2] = dp[0] [1] + 1 = 1. dp[1] [3] es 1 desde A != C y elegimos max{dp[1] [2], dp[0] [3]}. Y dp[1] [4] = dp[0] [3] + 1 = 1.

# # A B C B
# 0 0 0 0 0
B 0 0 1 1 1
B 0 ? ? ? ?
C 0 ? ? ? ?
B 0 ? ? ? ?

Ahora vamos a llenar la otra parte de la tabla:

# # A B C B
# 0 0 0 0 0
B 0 0 1 1 1
B 0 0 1 1 2
C 0 0 1 2 2
B 0 0 1 2 3

Así que la longitud de LCS es dp[4] [4] = 3.

Explicación en YouTube

Explicación en YouTube de Tushar Roy