Longest Common Substring (LCS)

Definition

Definition

The Longest Common Substring (LCS) Algorithm is a dynamic programming technique used to find the longest contiguous sequence of characters that is present in two given strings

Explanation

Building a matrix where each cell represents the length of the longest common substring ending at that position. It iteratively fills this matrix based on whether characters match in the two strings. The algorithm then traces back from the cell with the maximum value to reconstruct the actual substring

Guidance

• Create a matrix with dimensions (length of string 1 + 1) by (length of string 2 + 1)
• Initialize the first row and first column of the matrix with zeros
• Iterate through each cell of the matrix, starting from the second row and second column
• If the characters at the corresponding positions in the two strings match, set the value of the current cell to the value of the cell diagonally left and above it, plus one
• If the characters do not match, set the value of the current cell to zero
• Track the maximum value encountered during the iteration and its position
• Trace back from the cell with the maximum value to reconstruct the longest common substring

Tips

• optimize space usage by updating the matrix row by row instead of storing the entire matrix
• use efficient data structures like arrays instead of matrices for better memory utilization
• if memory is a concern, you can optimize further by using a rolling array approach, updating only the necessary portions of the matrix

Practice

Practice

longest_common_substring(string1, string2):
  m = length(string1)
  n = length(string2)
  max_length = 0
  end_index = 0

  # Initialize a matrix to store lengths of longest common suffixes
  # Initialize max_length and end_index to track the longest substring
  matrix = [[0] * (n + 1) for _ in range(m + 1)]

  # Iterate through each character of both strings
  for i from 1 to m:
    for j from 1 to n:
      if string1[i - 1] == string2[j - 1]:
        matrix[i][j] = matrix[i - 1][j - 1] + 1
        if matrix[i][j] > max_length:
          max_length = matrix[i][j]
          end_index = i
      else:
        matrix[i][j] = 0

  # Reconstruct the longest common substring
  longest_substring = string1[end_index - max_length : end_index]

  return longest_substring

Solution

package main

func longestCommonSubstring(str1, str2 string) string {
    var longest, current string
    matrix := make([][]int, len(str1)+1)
    for i := range matrix {
        matrix[i] = make([]int, len(str2)+1)
    }

    for i := 1; i <= len(str1); i++ {
        for j := 1; j <= len(str2); j++ {
            if str1[i-1] == str2[j-1] {
                matrix[i][j] = matrix[i-1][j-1] + 1
                current = str1[i-matrix[i][j] : i]
                if len(current) > len(longest) {
                    longest = current
                }
            }
        }
    }

    return longest
}

public class LongestCommonSubstring {

  public static String longestCommonSubstring(String str1, String str2) {
    int[][] matrix = new int[str1.length() + 1][str2.length() + 1];
    int maxLength = 0;
    int endIndex = 0;

    for (int i = 1; i <= str1.length(); i++) {
      for (int j = 1; j <= str2.length(); j++) {
        if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
          matrix[i][j] = matrix[i - 1][j - 1] + 1;
          if (matrix[i][j] > maxLength) {
            maxLength = matrix[i][j];
            endIndex = i;
          }
        }
      }
    }

    return str1.substring(endIndex - maxLength, endIndex);
  }
}

function longestCommonSubstring(str1, str2) {
  const matrix = Array.from({ length: str1.length + 1 }, () =>
    Array.from({ length: str2.length + 1 }, () => 0),
  );
  let longest = "";

  for (let i = 1; i <= str1.length; i++) {
    for (let j = 1; j <= str2.length; j++) {
      if (str1[i - 1] === str2[j - 1]) {
        matrix[i][j] = matrix[i - 1][j - 1] + 1;
        if (matrix[i][j] > longest.length) {
          longest = str1.substring(i - matrix[i][j], i);
        }
      }
    }
  }

  return longest;
}

fun longestCommonSubstring(str1: String, str2: String): String {
    val matrix = Array(str1.length + 1) { IntArray(str2.length + 1) }
    var longest = ""

    for (i in 1..str1.length) {
        for (j in 1..str2.length) {
            if (str1[i - 1] == str2[j - 1]) {
                matrix[i][j] = matrix[i - 1][j - 1] + 1
                if (matrix[i][j] > longest.length) {
                    longest = str1.substring(i - matrix[i][j], i)
                }
            }
        }
    }

    return longest
}

def longest_common_substring(str1, str2):
    matrix = [[0] * (len(str2) + 1) for _ in range(len(str1) + 1)]
    longest = ""

    for i in range(1, len(str1) + 1):
        for j in range(1, len(str2) + 1):
            if str1[i - 1] == str2[j - 1]:
                matrix[i][j] = matrix[i - 1][j - 1] + 1
                if matrix[i][j] > len(longest):
                    longest = str1[i - matrix[i][j] : i]

    return longest

fn longest_common_substring(str1: &str, str2: &str) -> String {
    let mut matrix = vec![vec![0; str2.len() + 1]; str1.len() + 1];
    let mut longest = String::new();

    for (i, c1) in str1.chars().enumerate() {
        for (j, c2) in str2.chars().enumerate() {
            if c1 == c2 {
                matrix[i + 1][j + 1] = matrix[i][j] + 1;
                if matrix[i + 1][j + 1] > longest.len() {
                    longest = str1[i + 1 - matrix[i + 1][j + 1]..=i].to_string();
                }
            }
        }
    }

    longest
}

function longestCommonSubstring(str1: string, str2: string): string {
  const matrix: number[][] = Array.from({ length: str1.length + 1 }, () =>
    Array.from({ length: str2.length + 1 }, () => 0),
  );
  let longest: string = "";

  for (let i = 1; i <= str1.length; i++) {
    for (let j = 1; j <= str2.length; j++) {
      if (str1[i - 1] === str2[j - 1]) {
        matrix[i][j] = matrix[i - 1][j - 1] + 1;
        if (matrix[i][j] > longest.length) {
          longest = str1.substring(i - matrix[i][j], i);
        }
      }
    }
  }

  return longest;
}