longestCommonSubsequence function

String longestCommonSubsequence(String s1, String s2)

Calculates the longest common subsequence between two strings

Implementation

String longestCommonSubsequence(String s1, String s2) {
  if (s1.isEmpty || s2.isEmpty) return '';

  final matrix = List<List<int>>.generate(
    s1.length + 1,
    (i) => List<int>.generate(s2.length + 1, (j) => 0),
  );

  // Fill in the matrix
  for (var i = 0; i < s1.length; i++) {
    for (var j = 0; j < s2.length; j++) {
      if (s1[i] == s2[j]) {
        matrix[i + 1][j + 1] = matrix[i][j] + 1;
      } else {
        matrix[i + 1][j + 1] = max(matrix[i + 1][j], matrix[i][j + 1]);
      }
    }
  }

  // Backtrack to find the LCS
  final lcs = StringBuffer();
  var i = s1.length;
  var j = s2.length;
  while (i > 0 && j > 0) {
    if (s1[i - 1] == s2[j - 1]) {
      lcs.write(s1[i - 1]);
      i--;
      j--;
    } else if (matrix[i - 1][j] > matrix[i][j - 1]) {
      i--;
    } else {
      j--;
    }
  }

  return lcs.toString().split('').reversed.join();
}