Longest Common Subsequence (LCS)

Definition

Definition

The Longest Common Subsequence (LCS) Algorithm is a dynamic programming approach used to find the longest subsequence present in given sequences

Explanation

The LCS algorithm aims to find the longest subsequence that is common to two given sequences. It starts by constructing a matrix where each cell represents the length of the longest common subsequence up to that point in the sequences. By iteratively filling this matrix, the algorithm efficiently computes the length of the longest common subsequence. It does so by comparing characters of the input sequences at each step. If the characters match, it adds one to the length of the LCS obtained without considering those characters. Otherwise, it takes the maximum length obtained so far without considering either of the characters. Finally, tracing back through the filled matrix yields the actual LCS

Guidance

• Initialize a matrix with dimensions [m+1][n+1] where m and n are the lengths of the 2 sequences
• Iterate through each cell of the matrix
• If the characters at the corresponding positions in the sequences match, increment the value in the current cell by 1 plus the value in the diagonal cell
• If the characters don't match, take the maximum of the values in the adjacent cells (above or to the left)
• Continue this process until the entire matrix is filled
• Trace back through the matrix from the bottom-right cell to reconstruct the LCS

Tips

• optimize space usage by realizing that you only need to keep track of the current row and the previous row of the matrix, reducing space complexity to O(min(m, n))
• ensure your implementation handles edge cases properly, such as empty sequences or sequences with no common elements

Practice

Practice

longest_common_subsequence(sequence1, sequence2):
  m = length(sequence1)
  n = length(sequence2)
  matrix = initialize_matrix(m, n)

  for i from 1 to m:
    for j from 1 to n:
      if sequence1[i-1] == sequence2[j-1]:
        matrix[i][j] = matrix[i-1][j-1] + 1
      else:
        matrix[i][j] = max(matrix[i-1][j], matrix[i][j-1])

  return reconstruct_lcs(matrix, sequence1, sequence2, m, n)

reconstruct_lcs(matrix, sequence1, sequence2, m, n):
  lcs = []
  i = m
  j = n

  while i > 0 and j > 0:
    if sequence1[i-1] == sequence2[j-1]:
      lcs.push(sequence1[i-1])
      i -= 1
      j -= 1
    else if matrix[i-1][j] > matrix[i][j-1]:
      i -= 1
    else:
      j -= 1

  return reverse(lcs)

initialize_matrix(m, n):
  matrix = new matrix with dimensions (m+1) x (n+1)
  for i from 0 to m:
    matrix[i][0] = 0
  for j from 0 to n:
    matrix[0][j] = 0
  return matrix

Solution

package main

func longestCommonSubsequence(text1 string, text2 string) int {
	m, n := len(text1), len(text2)
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			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])
			}
		}
	}
	return dp[m][n]
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

public class LongestCommonSubsequence {

  public int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length();
    int n = text2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
      for (int j = 1; j <= n; j++) {
        if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
          dp[i][j] = dp[i - 1][j - 1] + 1;
        } else {
          dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
      }
    }
    return dp[m][n];
  }
}

function longestCommonSubsequence(text1, text2) {
  const m = text1.length;
  const n = text2.length;
  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[m][n];
}

fun longestCommonSubsequence(text1: String, text2: String): Int {
    val m = text1.length
    val n = text2.length
    val dp = Array(m + 1) { IntArray(n + 1) }
    for (i in 1..m) {
        for (j in 1..n) {
            dp[i][j] = if (text1[i - 1] == text2[j - 1]) {
                dp[i - 1][j - 1] + 1
            } else {
                maxOf(dp[i - 1][j], dp[i][j - 1])
            }
        }
    }
    return dp[m][n]
}

def longestCommonSubsequence(text1: str, text2: str) -> int:
    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])
    return dp[m][n]

fn longest_common_subsequence(text1: &str, text2: &str) -> usize {
    let m = text1.len();
    let n = text2.len();
    let mut dp = vec![vec![0; n + 1]; m + 1];
    for i in 1..=m {
        for j in 1..=n {
            if text1.chars().nth(i - 1) == text2.chars().nth(j - 1) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = dp[i - 1][j].max(dp[i][j - 1]);
            }
        }
    }
    dp[m][n]
}

function longestCommonSubsequence(text1: string, text2: string): number {
  const m = text1.length;
  const n = text2.length;
  const dp: number[][] = Array.from({ length: m + 1 }, () =>
    Array(n + 1).fill(0),
  );
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[m][n];
}