Longest Common Subsequence (LCS) using Bottom-Up (Space-Optimization)
- In the above tabulation approach we are using L[i-1][j] and L[i][j] etc, here the L[i-1] will refers to the matrix L’s previous row and L[i] refers to the current row.
- We can do space optimization by using two vectors one is previous and another one is current.
- When the inner for loop exits we are initializing previous equal to current.
Below is the implementation:
// Dynamic Programming C++ implementation
// of LCS problem
#include <bits/stdc++.h>
using namespace std;
int longestCommonSubsequence(string& text1, string& text2)
{
int n = text1.size();
int m = text2.size();
// initializing 2 vectors of size m
vector<int> prev(m + 1, 0), cur(m + 1, 0);
for (int idx2 = 0; idx2 < m + 1; idx2++)
cur[idx2] = 0;
for (int idx1 = 1; idx1 < n + 1; idx1++) {
for (int idx2 = 1; idx2 < m + 1; idx2++) {
// if matching
if (text1[idx1 - 1] == text2[idx2 - 1])
cur[idx2] = 1 + prev[idx2 - 1];
// not matching
else
cur[idx2]
= 0 + max(cur[idx2 - 1], prev[idx2]);
}
prev = cur;
}
return cur[m];
}
int main()
{
string S1 = "AGGTAB";
string S2 = "GXTXAYB";
// Function call
cout << "Length of LCS is "
<< longestCommonSubsequence(S1, S2);
return 0;
}
// Dynamic Programming Java implementation of LCS problem
import java.util.Arrays;
public class GFG {
public static int longestCommonSubsequence(String text1, String text2) {
int n = text1.length();
int m = text2.length();
// Initializing 2 arrays of size m
int[] prev = new int[m + 1];
int[] cur = new int[m + 1];
for (int idx1 = 1; idx1 < n + 1; idx1++) {
for (int idx2 = 1; idx2 < m + 1; idx2++) {
// If matching
if (text1.charAt(idx1 - 1) == text2.charAt(idx2 - 1))
cur[idx2] = 1 + prev[idx2 - 1];
// Not matching
else
cur[idx2] = Math.max(cur[idx2 - 1], prev[idx2]);
}
prev = Arrays.copyOf(cur, m + 1);
}
return cur[m];
}
public static void main(String[] args) {
String S1 = "AGGTAB";
String S2 = "GXTXAYB";
// Function call
System.out.println("Length of LCS is " + longestCommonSubsequence(S1, S2));
}
}
def longestCommonSubsequence(text1, text2):
n = len(text1)
m = len(text2)
# Initializing two lists of size m
prev = [0] * (m + 1)
cur = [0] * (m + 1)
for idx1 in range(1, n + 1):
for idx2 in range(1, m + 1):
# If characters are matching
if text1[idx1 - 1] == text2[idx2 - 1]:
cur[idx2] = 1 + prev[idx2 - 1]
else:
# If characters are not matching
cur[idx2] = max(cur[idx2 - 1], prev[idx2])
prev = cur.copy()
return cur[m]
if __name__ == '__main__':
S1 = "AGGTAB"
S2 = "GXTXAYB"
# Function call
print("Length of LCS is", longestCommonSubsequence(S1, S2))
# This code is contributed by Rishabh Mathur
using System;
class Program
{
static int LongestCommonSubsequence(string text1, string text2)
{
int n = text1.Length;
int m = text2.Length;
// initializing 2 arrays of size m
int[] prev = new int[m + 1];
int[] cur = new int[m + 1];
for (int idx2 = 0; idx2 < m + 1; idx2++)
cur[idx2] = 0;
for (int idx1 = 1; idx1 < n + 1; idx1++)
{
for (int idx2 = 1; idx2 < m + 1; idx2++)
{
// if matching
if (text1[idx1 - 1] == text2[idx2 - 1])
cur[idx2] = 1 + prev[idx2 - 1];
// not matching
else
cur[idx2] = 0 + Math.Max(cur[idx2 - 1], prev[idx2]);
}
prev = cur;
}
return cur[m];
}
static void Main()
{
string S1 = "AGGTAB";
string S2 = "GXTXAYB";
// Function call
Console.WriteLine("Length of LCS is " + LongestCommonSubsequence(S1, S2));
}
}
function longestCommonSubsequence(text1, text2) {
const n = text1.length;
const m = text2.length;
// Initializing two arrays of size m
let prev = new Array(m + 1).fill(0);
let cur = new Array(m + 1).fill(0);
for (let idx2 = 0; idx2 < m + 1; idx2++) {
cur[idx2] = 0;
}
for (let idx1 = 1; idx1 < n + 1; idx1++) {
for (let idx2 = 1; idx2 < m + 1; idx2++) {
// If characters match
if (text1[idx1 - 1] === text2[idx2 - 1]) {
cur[idx2] = 1 + prev[idx2 - 1];
}
// If characters don't match
else {
cur[idx2] = Math.max(cur[idx2 - 1], prev[idx2]);
}
}
// Update the 'prev' array
prev = [...cur];
}
return cur[m];
}
// Main function
function main() {
const S1 = "AGGTAB";
const S2 = "GXTXAYB";
// Function call
console.log("Length of LCS is " + longestCommonSubsequence(S1, S2));
}
// Call the main function
main();
Output
Length of LCS is 4
Time Complexity: O(m * n), which remains the same.
Auxiliary Space: O(m) because the algorithm uses two arrays of size m.
Longest Common Subsequence (LCS)
Given two strings, S1 and S2, the task is to find the length of the Longest Common Subsequence, i.e. longest subsequence present in both of the strings.
A longest common subsequence (LCS) is defined as the longest subsequence which is common in all given input sequences.
Examples:
Input: S1 = “ABC”, S2 = “ACD”
Output: 2
Explanation: The longest subsequence which is present in both strings is “AC”.Input: S1 = “AGGTAB”, S2 = “GXTXAYB”
Output: 4
Explanation: The longest common subsequence is “GTAB”.Input: S1 = “ABC”, S2 = “CBA”
Output: 1
Explanation: There are three common subsequences of length 1, “A”, “B” and “C” and no common subsequence.of length more than 1.Input: S1 = “XYZW”, S2 = “XYWZ”
Output: 3
Explanation: There are two common subsequences of length 3 “XYZ”, and”XYW”, and no common subsequence. of length more than 3.
Contact Us