AntInLoop

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)