Longest Common Subsequence in DSA C - Build from Scratch

Longest Common Subsequence

📖 Scenario: You are working on a text comparison tool that helps find similarities between two strings. One important feature is to find the longest common subsequence (LCS) between two given strings. This helps in understanding how much two texts have in common, even if they are not exactly the same.

🎯 Goal: Build a program in C that calculates the length of the longest common subsequence between two given strings using dynamic programming.

📋 What You'll Learn

Create two string variables with exact values

Create a 2D array to store LCS lengths

Implement the dynamic programming logic to fill the 2D array

Print the length of the longest common subsequence

💡 Why This Matters

🌍 Real World

Longest common subsequence is used in text comparison tools, DNA sequence analysis, and version control systems to find similarities between sequences.

💼 Career

Understanding LCS helps in software development roles involving algorithms, bioinformatics, and data analysis where sequence comparison is important.

1

Create the input strings

Create two string variables called str1 and str2 with the exact values "AGGTAB" and "GXTXAYB" respectively.

DSA C

// Your code here

Hint

Use char str1[] = "AGGTAB"; and char str2[] = "GXTXAYB"; to create the strings.

2

Create the 2D array for LCS lengths

Create two integer variables m and n to store the lengths of str1 and str2. Then create a 2D integer array called lcs of size (m+1) x (n+1) to store the lengths of longest common subsequence for substrings.

DSA C

#include 

int main() {
    char str1[] = "AGGTAB";
    char str2[] = "GXTXAYB";

    // Your code here

    return 0;
}

Hint

Use strlen to get string lengths and declare int lcs[m+1][n+1];.

3

Fill the 2D array using dynamic programming

Use two nested for loops with variables i and j to fill the lcs array. Initialize the first row and first column with 0. For other cells, if str1[i-1] equals str2[j-1], set lcs[i][j] = lcs[i-1][j-1] + 1. Otherwise, set lcs[i][j] to the maximum of lcs[i-1][j] and lcs[i][j-1].

DSA C

#include 
#include 

int main() {
    char str1[] = "AGGTAB";
    char str2[] = "GXTXAYB";

    int m = strlen(str1);
    int n = strlen(str2);
    int lcs[m+1][n+1];

    // Your code here

    return 0;
}

Hint

Use nested loops from 0 to m and 0 to n. Initialize edges with 0. Use the conditions to fill lcs.

4

Print the length of the longest common subsequence

Print the value of lcs[m][n] using printf with the exact format: "Length of LCS is %d\n".

DSA C

#include 
#include 

int max(int a, int b) {
    return (a > b) ? a : b;
}

int main() {
    char str1[] = "AGGTAB";
    char str2[] = "GXTXAYB";

    int m = strlen(str1);
    int n = strlen(str2);
    int lcs[m+1][n+1];

    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0) {
                lcs[i][j] = 0;
            } else if (str1[i-1] == str2[j-1]) {
                lcs[i][j] = lcs[i-1][j-1] + 1;
            } else {
                lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1]);
            }
        }
    }

    // Your code here

    return 0;
}

Hint

Use printf("Length of LCS is %d\n", lcs[m][n]); to print the result.