Longest Common Subsequence in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of LCS length calculation

What is the output of the following C code that calculates the length of the Longest Common Subsequence (LCS) between two strings?

DSA C

int lcs_length(char *X, char *Y) {
    int m = strlen(X);
    int n = strlen(Y);
    int L[m+1][n+1];
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0)
                L[i][j] = 0;
            else if (X[i-1] == Y[j-1])
                L[i][j] = L[i-1][j-1] + 1;
            else
                L[i][j] = (L[i-1][j] > L[i][j-1]) ? L[i-1][j] : L[i][j-1];
        }
    }
    return L[m][n];
}

int main() {
    char X[] = "AGGTAB";
    char Y[] = "GXTXAYB";
    printf("%d", lcs_length(X, Y));
    return 0;
}

A 5

B 7

C 6

D 4

💡 Hint

Trace the matching characters between the two strings and count the longest sequence.

The longest common subsequence between "AGGTAB" and "GXTXAYB" is "GTAB", which has length 4 (option A).

❓ Predict Output

intermediate

Output of LCS sequence reconstruction

What is the output of the following C code that reconstructs and prints the Longest Common Subsequence (LCS) between two strings?

DSA C

#include <stdio.h>
#include <string.h>

void print_lcs(char *X, char *Y) {
    int m = strlen(X);
    int n = strlen(Y);
    int L[m+1][n+1];
    for (int i = 0; i <= m; i++)
        for (int j = 0; j <= n; j++)
            L[i][j] = 0;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (X[i-1] == Y[j-1])
                L[i][j] = L[i-1][j-1] + 1;
            else
                L[i][j] = (L[i-1][j] > L[i][j-1]) ? L[i-1][j] : L[i][j-1];
        }
    }
    int index = L[m][n];
    char lcs[index+1];
    lcs[index] = '\0';
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (X[i-1] == Y[j-1]) {
            lcs[index-1] = X[i-1];
            i--;
            j--;
            index--;
        } else if (L[i-1][j] > L[i][j-1])
            i--;
        else
            j--;
    }
    printf("%s", lcs);
}

int main() {
    char X[] = "ABCBDAB";
    char Y[] = "BDCABA";
    print_lcs(X, Y);
    return 0;
}

A BCBA

B BDAB

C BCAB

D BDCB

💡 Hint

Trace back from the bottom-right of the LCS table to find the sequence.

The longest common subsequence between "ABCBDAB" and "BDCABA" is "BDAB". The code reconstructs this sequence correctly and prints it.

🧠 Conceptual

advanced

Time complexity of LCS dynamic programming solution

What is the time complexity of the classic dynamic programming solution to find the length of the Longest Common Subsequence of two strings of lengths m and n?

A O(m + n)

B O(m^2 + n^2)

C O(m * n)

D O(2^(m+n))

💡 Hint

Consider the nested loops iterating over both strings.

The dynamic programming solution fills a 2D table of size m by n, so it takes O(m * n) time.

🔧 Debug

advanced

Identify the error in LCS length calculation code

What error will the following C code produce when trying to calculate the LCS length?

DSA C

int lcs_length(char *X, char *Y) {
    int m = strlen(X);
    int n = strlen(Y);
    int *L = malloc((m+1)*(n+1)*sizeof(int));
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0)
                L[i*(n+1)+j] = 0;
            else if (X[i-1] == Y[j-1])
                L[i*(n+1)+j] = L[(i-1)*(n+1)+(j-1)] + 1;
            else {
                int a = L[(i-1)*(n+1)+j];
                int b = L[i*(n+1)+(j-1)];
                L[i*(n+1)+j] = (a > b) ? a : b;
            }
        }
    }
    int result = L[m*(n+1)+n];
    free(L);
    return result;
}

int main() {
    char X[] = "ABC";
    char Y[] = "AC";
    printf("%d", lcs_length(X, Y));
    return 0;
}

A No error, outputs 2

B Segmentation fault due to invalid memory access

C Runtime error: double free detected

D Compilation error: missing #include <stdlib.h>

💡 Hint

Check if all required headers are included for used functions.

The code uses malloc and free but does not include , so it will cause a compilation error.

🚀 Application

expert

Number of distinct LCS sequences

Given two strings X = "ABCBDAB" and Y = "BDCABA", how many distinct Longest Common Subsequences do they have?

A 3

B 4

C 2

D 1

💡 Hint

Consider all sequences of length equal to the LCS length and check which are distinct.

The LCS length is 4. The distinct LCS sequences are "BCAB", "BDAB", and "BCBA". So there are 3 distinct sequences.