Longest Common Subsequence (LCS) Code Implementations
Complete Longest Common Subsequence (LCS) code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.
Read Longest Common Subsequence (LCS) Guide ยท Launch Interactive Visualizer
C++ Implementation
// Longest Common Subsequence Implementation in C++
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <set>
#include <algorithm>
class LongestCommonSubsequence {
public:
static int longestCommonSubsequence(const std::string& text1, const std::string& text2) {
int m = text1.length();
int n = text2.length();
std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
// Build the DP table
for (int i = 1; i <= m; i++) {
for (int 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] = std::max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
// Space-optimized version using 1D array
static int longestCommonSubsequenceOptimized(const std::string& text1, const std::string& text2) {
int m = text1.length();
int n = text2.length();
// Use the shorter string for the DP array
if (m < n) {
std::swap(text1, text2);
std::swap(m, n);
}
std::vector<int> dp(n + 1, 0);
for (int i = 1; i <= m; i++) {
int prev = 0;
for (int j = 1; j <= n; j++) {
int temp = dp[j];
if (text1[i - 1] == text2[j - 1]) {
dp[j] = prev + 1;
} else {
dp[j] = std::max(dp[j], dp[j - 1]);
}
prev = temp;
}
}
return dp[n];
}
// LCS with subsequence reconstruction
struct LCSResult {
int length;
std::string subsequence;
LCSResult(int len, const std::string& sub) : length(len), subsequence(sub) {}
};
static LCSResult longestCommonSubsequenceWithString(const std::string& text1, const std::string& text2) {
int m = text1.length();
int n = text2.length();
std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
// Build the DP table
for (int i = 1; i <= m; i++) {
for (int 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] = std::max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
// Reconstruct the subsequence
std::string subsequence;
int i = m, j = n;
while (i > 0 && j > 0) {
if (text1[i - 1] == text2[j - 1]) {
subsequence = text1[i - 1] + subsequence;
i--;
j--;
} else if (dp[i - 1][j] > dp[i][j - 1]) {
i--;
} else {
j--;
}
}
return LCSResult(dp[m][n], subsequence);
}
// LCS with memoization (top-down approach)
static int longestCommonSubsequenceMemo(const std::string& text1, const std::string& text2) {
std::unordered_map<std::string, int> memo;
return solveMemo(text1, text2, text1.length(), text2.length(), memo);
}
private:
static int solveMemo(const std::string& text1, const std::string& text2,
int i, int j, std::unordered_map<std::string, int>& memo) {
if (i == 0 || j == 0) return 0;
std::string key = std::to_string(i) + "," + std::to_string(j);
if (memo.find(key) != memo.end()) return memo[key];
int result;
if (text1[i - 1] == text2[j - 1]) {
result = solveMemo(text1, text2, i - 1, j - 1, memo) + 1;
} else {
result = std::max(
solveMemo(text1, text2, i - 1, j, memo),
solveMemo(text1, text2, i, j - 1, memo)
);
}
memo[key] = result;
return result;
}
public:
// Helper function to check if a string is a subsequence of another
static bool isSubsequence(const std::string& s, const std::string& t) {
int j = 0;
for (int i = 0; i < s.length() && j < t.length(); i++) {
if (s[i] == t[j]) {
j++;
}
}
return j == t.length();
}
// LCS for multiple strings
static int longestCommonSubsequenceMultiple(const std::vector<std::string>& strings) {
if (strings.empty()) return 0;
if (strings.size() == 1) return strings[0].length();
// Find the shortest string
std::string shortest = strings[0];
for (const auto& s : strings) {
if (s.length() < shortest.length()) {
shortest = s;
}
}
// Generate all possible subsequences
std::set<std::string> subsequences;
generateSubsequences(shortest, 0, "", subsequences);
int maxLength = 0;
for (const auto& subseq : subsequences) {
if (!subseq.empty()) {
bool isCommon = true;
for (const auto& s : strings) {
if (!isSubsequence(s, subseq)) {
isCommon = false;
break;
}
}
if (isCommon) {
maxLength = std::max(maxLength, (int)subseq.length());
}
}
}
return maxLength;
}
private:
static void generateSubsequences(const std::string& s, int index, const std::string& current,
std::set<std::string>& result) {
if (index == s.length()) {
if (!current.empty()) {
result.insert(current);
}
return;
}
// Include current character
generateSubsequences(s, index + 1, current + s[index], result);
// Exclude current character
generateSubsequences(s, index + 1, current, result);
}
};JAVA Implementation
// Longest Common Subsequence Implementation in Java
public class LongestCommonSubsequence {
public static int longestCommonSubsequence(String text1, String text2) {
int m = text1.length();
int n = text2.length();
int[][] dp = new int[m + 1][n + 1];
// Build the DP table
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];
}
// Space-optimized version using 1D array
public static int longestCommonSubsequenceOptimized(String text1, String text2) {
int m = text1.length();
int n = text2.length();
// Use the shorter string for the DP array
if (m < n) {
String temp = text1;
text1 = text2;
text2 = temp;
int tempLen = m;
m = n;
n = tempLen;
}
int[] dp = new int[n + 1];
for (int i = 1; i <= m; i++) {
int prev = 0;
for (int j = 1; j <= n; j++) {
int temp = dp[j];
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[j] = prev + 1;
} else {
dp[j] = Math.max(dp[j], dp[j - 1]);
}
prev = temp;
}
}
return dp[n];
}
// LCS with subsequence reconstruction
public static class LCSResult {
public int length;
public String subsequence;
public LCSResult(int length, String subsequence) {
this.length = length;
this.subsequence = subsequence;
}
}
public static LCSResult longestCommonSubsequenceWithString(String text1, String text2) {
int m = text1.length();
int n = text2.length();
int[][] dp = new int[m + 1][n + 1];
// Build the DP table
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]);
}
}
}
// Reconstruct the subsequence
java.util.List<Character> subsequence = new java.util.ArrayList<>();
int i = m, j = n;
while (i > 0 && j > 0) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
subsequence.add(0, text1.charAt(i - 1));
i--;
j--;
} else if (dp[i - 1][j] > dp[i][j - 1]) {
i--;
} else {
j--;
}
}
StringBuilder result = new StringBuilder();
for (char c : subsequence) {
result.append(c);
}
return new LCSResult(dp[m][n], result.toString());
}
// LCS with memoization (top-down approach)
public static int longestCommonSubsequenceMemo(String text1, String text2) {
java.util.Map<String, Integer> memo = new java.util.HashMap<>();
return solveMemo(text1, text2, text1.length(), text2.length(), memo);
}
private static int solveMemo(String text1, String text2, int i, int j, java.util.Map<String, Integer> memo) {
if (i == 0 || j == 0) return 0;
String key = i + "," + j;
if (memo.containsKey(key)) return memo.get(key);
int result;
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
result = solveMemo(text1, text2, i - 1, j - 1, memo) + 1;
} else {
result = Math.max(
solveMemo(text1, text2, i - 1, j, memo),
solveMemo(text1, text2, i, j - 1, memo)
);
}
memo.put(key, result);
return result;
}
// Helper function to check if a string is a subsequence of another
public static boolean isSubsequence(String s, String t) {
int j = 0;
for (int i = 0; i < s.length() && j < t.length(); i++) {
if (s.charAt(i) == t.charAt(j)) {
j++;
}
}
return j == t.length();
}
// LCS for multiple strings
public static int longestCommonSubsequenceMultiple(String[] strings) {
if (strings.length == 0) return 0;
if (strings.length == 1) return strings[0].length();
// Find the shortest string
String shortest = strings[0];
for (String s : strings) {
if (s.length() < shortest.length()) {
shortest = s;
}
}
// Generate all possible subsequences and check
java.util.Set<String> subsequences = new java.util.HashSet<>();
generateSubsequences(shortest, 0, "", subsequences);
int maxLength = 0;
for (String subseq : subsequences) {
if (subseq.length() > 0) {
boolean isCommon = true;
for (String s : strings) {
if (!isSubsequence(s, subseq)) {
isCommon = false;
break;
}
}
if (isCommon) {
maxLength = Math.max(maxLength, subseq.length());
}
}
}
return maxLength;
}
private static void generateSubsequences(String s, int index, String current, java.util.Set<String> result) {
if (index == s.length()) {
if (current.length() > 0) {
result.add(current);
}
return;
}
// Include current character
generateSubsequences(s, index + 1, current + s.charAt(index), result);
// Exclude current character
generateSubsequences(s, index + 1, current, result);
}
}JAVASCRIPT Implementation
// Longest Common Subsequence Implementation in JavaScript
function longestCommonSubsequence(text1, text2) {
const m = text1.length;
const n = text2.length;
const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0));
// Build the DP table
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];
}
// Space-optimized version using 1D array
function longestCommonSubsequenceOptimized(text1, text2) {
const m = text1.length;
const n = text2.length;
// Use the shorter string for the DP array
if (m < n) {
[text1, text2] = [text2, text1];
[m, n] = [n, m];
}
const dp = Array(n + 1).fill(0);
for (let i = 1; i <= m; i++) {
let prev = 0;
for (let j = 1; j <= n; j++) {
const temp = dp[j];
if (text1[i - 1] === text2[j - 1]) {
dp[j] = prev + 1;
} else {
dp[j] = Math.max(dp[j], dp[j - 1]);
}
prev = temp;
}
}
return dp[n];
}
// LCS with subsequence reconstruction
function longestCommonSubsequenceWithString(text1, text2) {
const m = text1.length;
const n = text2.length;
const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0));
// Build the DP table
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]);
}
}
}
// Reconstruct the subsequence
const subsequence = [];
let i = m, j = n;
while (i > 0 && j > 0) {
if (text1[i - 1] === text2[j - 1]) {
subsequence.unshift(text1[i - 1]);
i--;
j--;
} else if (dp[i - 1][j] > dp[i][j - 1]) {
i--;
} else {
j--;
}
}
return {
length: dp[m][n],
subsequence: subsequence.join('')
};
}
// LCS for multiple strings
function longestCommonSubsequenceMultiple(strings) {
if (strings.length === 0) return 0;
if (strings.length === 1) return strings[0].length;
// Find the shortest string
const shortest = strings.reduce((a, b) => a.length < b.length ? a : b);
const otherStrings = strings.filter(s => s !== shortest);
let maxLength = 0;
// Generate all possible subsequences of the shortest string
const generateSubsequences = (str, index = 0, current = '') => {
if (index === str.length) {
if (current.length > 0) {
// Check if this subsequence exists in all other strings
const isCommon = otherStrings.every(s => isSubsequence(s, current));
if (isCommon) {
maxLength = Math.max(maxLength, current.length);
}
}
return;
}
// Include current character
generateSubsequences(str, index + 1, current + str[index]);
// Exclude current character
generateSubsequences(str, index + 1, current);
};
generateSubsequences(shortest);
return maxLength;
}
// Helper function to check if a string is a subsequence of another
function isSubsequence(s, t) {
let j = 0;
for (let i = 0; i < s.length && j < t.length; i++) {
if (s[i] === t[j]) {
j++;
}
}
return j === t.length;
}
// LCS with memoization (top-down approach)
function longestCommonSubsequenceMemo(text1, text2) {
const memo = new Map();
function solve(i, j) {
if (i === 0 || j === 0) return 0;
const key = i + ',' + j;
if (memo.has(key)) return memo.get(key);
let result;
if (text1[i - 1] === text2[j - 1]) {
result = solve(i - 1, j - 1) + 1;
} else {
result = Math.max(solve(i - 1, j), solve(i, j - 1));
}
memo.set(key, result);
return result;
}
return solve(text1.length, text2.length);
}PYTHON Implementation
# Longest Common Subsequence Implementation in Python
def longest_common_subsequence(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Build the DP table
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]
# Space-optimized version using 1D array
def longest_common_subsequence_optimized(text1, text2):
m, n = len(text1), len(text2)
# Use the shorter string for the DP array
if m < n:
text1, text2 = text2, text1
m, n = n, m
dp = [0] * (n + 1)
for i in range(1, m + 1):
prev = 0
for j in range(1, n + 1):
temp = dp[j]
if text1[i - 1] == text2[j - 1]:
dp[j] = prev + 1
else:
dp[j] = max(dp[j], dp[j - 1])
prev = temp
return dp[n]
# LCS with subsequence reconstruction
def longest_common_subsequence_with_string(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Build the DP table
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])
# Reconstruct the subsequence
subsequence = []
i, j = m, n
while i > 0 and j > 0:
if text1[i - 1] == text2[j - 1]:
subsequence.append(text1[i - 1])
i -= 1
j -= 1
elif dp[i - 1][j] > dp[i][j - 1]:
i -= 1
else:
j -= 1
return {
'length': dp[m][n],
'subsequence': ''.join(reversed(subsequence))
}
# LCS for multiple strings
def longest_common_subsequence_multiple(strings):
if not strings:
return 0
if len(strings) == 1:
return len(strings[0])
# Find the shortest string
shortest = min(strings, key=len)
other_strings = [s for s in strings if s != shortest]
max_length = 0
def generate_subsequences(s, index=0, current=''):
nonlocal max_length
if index == len(s):
if current and all(is_subsequence(s, current) for s in other_strings):
max_length = max(max_length, len(current))
return
# Include current character
generate_subsequences(s, index + 1, current + s[index])
# Exclude current character
generate_subsequences(s, index + 1, current)
generate_subsequences(shortest)
return max_length
# Helper function to check if a string is a subsequence of another
def is_subsequence(s, t):
j = 0
for i in range(len(s)):
if j < len(t) and s[i] == t[j]:
j += 1
return j == len(t)
# LCS with memoization (top-down approach)
def longest_common_subsequence_memo(text1, text2):
memo = {}
def solve(i, j):
if i == 0 or j == 0:
return 0
if (i, j) in memo:
return memo[(i, j)]
if text1[i - 1] == text2[j - 1]:
result = solve(i - 1, j - 1) + 1
else:
result = max(solve(i - 1, j), solve(i, j - 1))
memo[(i, j)] = result
return result
return solve(len(text1), len(text2))
# LCS with all possible subsequences
def all_longest_common_subsequences(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Build the DP table
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])
# Find all LCS using backtracking
def backtrack(i, j, current):
if i == 0 or j == 0:
if current:
subsequences.add(''.join(reversed(current)))
return
if text1[i - 1] == text2[j - 1]:
backtrack(i - 1, j - 1, current + [text1[i - 1]])
else:
if dp[i - 1][j] >= dp[i][j - 1]:
backtrack(i - 1, j, current)
if dp[i][j - 1] >= dp[i - 1][j]:
backtrack(i, j - 1, current)
subsequences = set()
backtrack(m, n, [])
return list(subsequences)