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.

Practice

1. What does the Longest Common Subsequence (LCS) between two strings represent?

easy

A. The longest sequence of characters that appear in both strings in the same order, but not necessarily consecutively.

B. The longest substring that appears in both strings consecutively.

C. The total number of characters in both strings combined.

D. The shortest sequence of characters that can be removed to make the strings identical.

Solution

1. Step 1: Understand the definition of LCS

   The LCS is a sequence that appears in both strings in the same order but not necessarily next to each other.

2. Step 2: Differentiate from substring and other concepts

   Unlike substring, LCS does not require characters to be consecutive. It is about order and presence.

3. Final Answer:

   The longest sequence of characters that appear in both strings in the same order, but not necessarily consecutively. -> Option A

4. Quick Check:

   LCS = longest ordered common sequence [OK]

Hint: LCS is about order, not consecutive characters [OK]

Common Mistakes:

• Confusing LCS with longest common substring
• Thinking characters must be consecutive
• Mixing LCS with string length or edits

2. Which of the following is the correct way to declare a 2D array in C for storing LCS lengths of two strings of length m and n?

easy

A. int lcs[m][n];

B. int lcs[m-1][n-1];

C. int lcs[m+1][n+1];

D. int lcs[m*n];

Solution

1. Step 1: Understand LCS table size requirements

   We need a table of size (m+1) x (n+1) to include empty prefixes for both strings.

2. Step 2: Check array declaration syntax

   int lcs[m+1][n+1]; correctly declares int lcs[m+1][n+1]; which fits the DP table size.

3. Final Answer:

   int lcs[m+1][n+1]; -> Option C

4. Quick Check:

   DP table size = (m+1) x (n+1) [OK]

Hint: Add 1 to lengths for DP table size [OK]

Common Mistakes:

• Using m or n instead of m+1 or n+1
• Declaring 1D array instead of 2D
• Using multiplication instead of 2D array

3. What is the output of the following C code snippet that computes the length of LCS for strings "ABCBDAB" and "BDCABA"?

int main() {
    char X[] = "ABCBDAB";
    char Y[] = "BDCABA";
    int m = 7, n = 6;
    int lcs[8][7];
    for (int i = 0; i <= m; i++) lcs[i][0] = 0;
    for (int j = 0; j <= n; j++) lcs[0][j] = 0;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (X[i-1] == Y[j-1])
                lcs[i][j] = lcs[i-1][j-1] + 1;
            else
                lcs[i][j] = (lcs[i-1][j] > lcs[i][j-1]) ? lcs[i-1][j] : lcs[i][j-1];
        }
    }
    printf("%d", lcs[m][n]);
    return 0;
}

medium

A. 6

B. 3

C. 5

D. 4

Solution

1. Step 1: Understand the DP table filling

   The code fills the LCS table using standard DP approach comparing characters of X and Y.

2. Step 2: Calculate LCS length for given strings

   The LCS of "ABCBDAB" and "BDCABA" is "BCBA" or "BDAB" with length 4, but careful tracing shows length 4 is correct. However, the code prints lcs[m][n], which is 4.

3. Step 3: Re-evaluate LCS length

   Actually, the longest common subsequence length is 4 or 5? Let's check carefully:
   - "BCBA" length 4
   - "BDAB" length 4
   - But "BCABA" is not a subsequence.
   Rechecking the classic example, the LCS length is 4.
   But the code output is 4, so 4 is correct.

4. Final Answer:

   4 -> Option D

5. Quick Check:

   LCS length for given strings = 4 [OK]

Hint: Trace DP table or recall classic LCS example [OK]

Common Mistakes:

• Confusing LCS length with substring length
• Off-by-one errors in indexing
• Misreading the strings or code logic

4. Identify the error in the following C code snippet intended to compute the LCS length of two strings X and Y:

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

medium

A. Indexing X[i] and Y[j] should be X[i-1] and Y[j-1].

B. Array size should be lcs[m+1][n+1] instead of lcs[m][n].

C. Initialization loops should start from 1, not 0.

D. Return statement should be lcs[m-1][n-1] instead of lcs[m][n].

Solution

1. Step 1: Check array size and initialization

   The array size (m+1) x (n+1) and initialization loops are correct for the DP table.

2. Step 2: Check indexing of characters in strings

   Strings in C are 0-indexed, but loops run from 1 to m/n, so characters should be accessed as X[i-1] and Y[j-1].

3. Final Answer:

   Indexing X[i] and Y[j] should be X[i-1] and Y[j-1]. -> Option A

4. Quick Check:

   String indexing off by one error [OK]

Hint: Remember C strings start at index 0 [OK]

Common Mistakes:

• Using wrong indices for string characters
• Ignoring array size for DP table
• Incorrect initialization loop ranges

5. Given two strings X = "AGGTAB" and Y = "GXTXAYB", write a C function to print the actual Longest Common Subsequence (LCS) string, not just its length. Which approach correctly reconstructs the LCS from the DP table?

hard

A. Start from lcs[0][0], move right or down to find matching characters and build LCS forward.

B. Start from lcs[m][n], move diagonally up-left if characters match, else move in direction of larger value until reaching lcs[0][0].

C. Use recursion without memoization to print LCS directly from strings.

D. Print characters from X that appear anywhere in Y without order consideration.

Solution

1. Step 1: Understand LCS reconstruction from DP table

   After filling the DP table, start from bottom-right cell lcs[m][n] and move backwards.

2. Step 2: Move diagonally if characters match, else move towards larger neighbor

   If characters match, include that character and move diagonally up-left; else move to the cell with larger value (up or left).

3. Step 3: Continue until reaching lcs[0][0]

   Collect characters in reverse order and then reverse them to get the LCS string.

4. Final Answer:

   Start from lcs[m][n], move diagonally up-left if characters match, else move in direction of larger value until reaching lcs[0][0]. -> Option B

5. Quick Check:

   Backtrack DP table from bottom-right to reconstruct LCS [OK]

Hint: Backtrack DP table from bottom-right to get LCS [OK]

Common Mistakes:

• Trying to build LCS forward from top-left
• Ignoring order of characters in reconstruction
• Printing characters without checking DP table values