Longest Common Subsequence in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare the 2D array for dynamic programming.

DSA C

int dp[[1]][100];

Drag options to blanks, or click blank then click option'

A101

B100

C50

Dstrlen(s1)

Attempts:

3 left

💡 Hint

Common Mistakes

Using the exact string length without adding 1 causes out-of-bound errors.

The dp array size should be one more than the string length to include the empty substring case.

2fill in blank

medium

Complete the code to initialize the first row of dp with zeros.

DSA C

for (int j = 0; j <= m; j++) dp[0][j] = [1];

Drag options to blanks, or click blank then click option'

Aj

B1

C0

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing with 1 or other values causes incorrect LCS calculation.

The first row represents empty prefix of s1, so LCS length is zero for all prefixes of s2.

3fill in blank

hard

Fix the error in the condition to check if characters match.

DSA C

if (s1[i - 1] [1] s2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;

Drag options to blanks, or click blank then click option'

A==

B<

C>

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '!=' causes wrong LCS length calculation.

We add 1 to dp[i-1][j-1] only if characters at current positions are equal.

4fill in blank

hard

Fill in the blank to choose the maximum LCS length from previous states.

DSA C

else dp[i][j] = (dp[i - 1][j] [1] dp[i][j - 1]) ? dp[i - 1][j] : dp[i][j - 1];

Drag options to blanks, or click blank then click option'

Amin

B<

Cmax

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Using min or wrong comparison leads to incorrect LCS length.

We take the maximum of dp[i-1][j] and dp[i][j-1] to find the longest subsequence so far.

5fill in blank

hard

Fill all three blanks to complete the loop for filling dp table.

DSA C

for (int i = 1; i [1] n; i++) {
    for (int j = 1; j [2] m; j++) {
        if (s1[i - 1] == s2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + [3];
        else dp[i][j] = (dp[i - 1][j] > dp[i][j - 1]) ? dp[i - 1][j] : dp[i][j - 1];
    }
}

Drag options to blanks, or click blank then click option'

A<=

B<

C1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' excludes last character, adding 0 does not increase length.

The loops run from 1 to length inclusive, and we add 1 when characters match.