Longest Common Subsequence in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of LCS length calculation

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

DSA Rust

fn lcs_length(s1: &str, s2: &str) -> usize {
    let m = s1.len();
    let n = s2.len();
    let s1_bytes = s1.as_bytes();
    let s2_bytes = s2.as_bytes();
    let mut dp = vec![vec![0; n + 1]; m + 1];

    for i in 1..=m {
        for j in 1..=n {
            if s1_bytes[i - 1] == s2_bytes[j - 1] {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = dp[i - 1][j].max(dp[i][j - 1]);
            }
        }
    }
    dp[m][n]
}

fn main() {
    let s1 = "AGGTAB";
    let s2 = "GXTXAYB";
    println!("{}", lcs_length(s1, s2));
}

A 3

B 5

C 4

D 6

💡 Hint

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

The longest common subsequence between "AGGTAB" and "GXTXAYB" is "GTAB" which has length 4.

The code returns 4, so option C is correct.

❓ Predict Output

intermediate

Output of LCS sequence reconstruction

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

DSA Rust

fn lcs_sequence(s1: &str, s2: &str) -> String {
    let m = s1.len();
    let n = s2.len();
    let s1_bytes = s1.as_bytes();
    let s2_bytes = s2.as_bytes();
    let mut dp = vec![vec![0; n + 1]; m + 1];

    for i in 1..=m {
        for j in 1..=n {
            if s1_bytes[i - 1] == s2_bytes[j - 1] {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = dp[i - 1][j].max(dp[i][j - 1]);
            }
        }
    }

    let mut i = m;
    let mut j = n;
    let mut lcs = Vec::new();
    while i > 0 && j > 0 {
        if s1_bytes[i - 1] == s2_bytes[j - 1] {
            lcs.push(s1_bytes[i - 1]);
            i -= 1;
            j -= 1;
        } else if dp[i - 1][j] > dp[i][j - 1] {
            i -= 1;
        } else {
            j -= 1;
        }
    }
    lcs.reverse();
    String::from_utf8(lcs).unwrap()
}

fn main() {
    let s1 = "ABCBDAB";
    let s2 = "BDCABA";
    println!("{}", lcs_sequence(s1, s2));
}

A BDAB

B BDA

C BCAB

D BCBA

💡 Hint

Follow the backtracking from the dp table to find the correct subsequence.

The longest common subsequence between "ABCBDAB" and "BDCABA" is "BDAB".

The code reconstructs this sequence by backtracking the dp table.

🔧 Debug

advanced

Identify the error in LCS length code

This Rust code attempts to calculate the length of the Longest Common Subsequence (LCS) but produces incorrect results. What is the error?

DSA Rust

fn lcs_length(s1: &str, s2: &str) -> usize {
    let m = s1.len();
    let n = s2.len();
    let s1_bytes = s1.as_bytes();
    let s2_bytes = s2.as_bytes();
    let mut dp = vec![vec![0; n]; m];

    for i in 1..m {
        for j in 1..n {
            if s1_bytes[i] == s2_bytes[j] {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = dp[i - 1][j].max(dp[i][j - 1]);
            }
        }
    }
    dp[m - 1][n - 1]
}

fn main() {
    let s1 = "ABC";
    let s2 = "AC";
    println!("{}", lcs_length(s1, s2));
}

A The loops start from 1 instead of 0, skipping the first characters comparison.

B The final return dp[m-1][n-1] is incorrect; it should be dp[m][n].

C The code uses s1_bytes[i] and s2_bytes[j] without checking bounds, causing panic.

D The dp vector is initialized with size m x n instead of (m+1) x (n+1), causing index errors.

💡 Hint

Check how the dp table is sized and accessed in the loops.

The dp table must be sized (m+1) x (n+1) to handle base cases and avoid index errors.

Initializing dp with m x n causes out-of-bound accesses when i or j equals m or n.

🧠 Conceptual

advanced

Time complexity of LCS dynamic programming solution

What is the time complexity of the standard 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 * n)

C O(2^(m + n))

D O(m^2 + n^2)

💡 Hint

Consider the nested loops iterating over both strings.

The DP solution uses a 2D table of size m x n and fills each cell once.

Thus, the time complexity is O(m * n).

🚀 Application

expert

Longest Common Subsequence in DNA sequences

Given two DNA sequences represented as strings containing only 'A', 'C', 'G', 'T', which Rust function call correctly computes the length of their Longest Common Subsequence?

DSA Rust

fn lcs_length(s1: &str, s2: &str) -> usize {
    let m = s1.len();
    let n = s2.len();
    let s1_bytes = s1.as_bytes();
    let s2_bytes = s2.as_bytes();
    let mut dp = vec![vec![0; n + 1]; m + 1];

    for i in 1..=m {
        for j in 1..=n {
            if s1_bytes[i - 1] == s2_bytes[j - 1] {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = dp[i - 1][j].max(dp[i][j - 1]);
            }
        }
    }
    dp[m][n]
}

fn main() {
    // Which call is correct?
}

A println!("{}", lcs_length("ACGTACGT", "TACG"));

B println!("{}", lcs_length("ACGT", "XYZ"));

C println!("{}", lcs_length("ACGT", "ACGTN"));

D println!("{}", lcs_length("ACGT", "acgt"));

💡 Hint

DNA sequences only contain 'A', 'C', 'G', 'T' uppercase letters.

Option A uses valid DNA sequences with only 'A', 'C', 'G', 'T'.

Option A contains invalid characters 'X', 'Y', 'Z'.

Option A contains 'N' which is not standard DNA base here.

Option A uses lowercase letters which differ from uppercase ASCII codes.

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 exactly the same in both strings.

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

D. The total number of characters that differ between the two strings.

Solution

1. Step 1: Understand the definition of LCS

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

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 keeps order, skips gaps, unlike substring [OK]

Common Mistakes:

• Confusing LCS with longest common substring
• Thinking characters must be consecutive
• Mixing LCS with edit distance

2. Which of the following Rust function signatures correctly represents a function to compute LCS length between two string slices?

easy

A. fn lcs_length(s1: &str, s2: &str) -> bool

B. fn lcs_length(s1: String, s2: String) -> &str

C. fn lcs_length(s1: &String, s2: &String) -> String

D. fn lcs_length(s1: &str, s2: &str) -> usize

Solution

1. Step 1: Identify correct parameter types for string inputs

   Using &str is idiomatic for string slices in Rust, allowing borrowing without ownership transfer.

2. Step 2: Identify correct return type for LCS length

   LCS length is a number, so usize is appropriate. Returning &str or String is incorrect for length.

3. Final Answer:

   fn lcs_length(s1: &str, s2: &str) -> usize -> Option D

4. Quick Check:

   Input: &str, Output: usize for length [OK]

Hint: Use &str for inputs and usize for length output [OK]

Common Mistakes:

• Returning &str or String instead of length
• Using owned String unnecessarily
• Returning bool instead of length

3. What is the output of the following Rust code snippet that computes the LCS length of "AGGTAB" and "GXTXAYB"?

fn main() {
    let s1 = "AGGTAB";
    let s2 = "GXTXAYB";
    let lcs_len = lcs_length(s1, s2);
    println!("{}", lcs_len);
}

fn lcs_length(s1: &str, s2: &str) -> usize {
    let m = s1.len();
    let n = s2.len();
    let mut dp = vec![vec![0; n + 1]; m + 1];
    for i in 1..=m {
        for j in 1..=n {
            if s1.as_bytes()[i - 1] == s2.as_bytes()[j - 1] {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = dp[i - 1][j].max(dp[i][j - 1]);
            }
        }
    }
    dp[m][n]
}

medium

A. 6

B. 3

C. 4

D. 5

Solution

1. Step 1: Understand the input strings and LCS algorithm

   Strings are "AGGTAB" and "GXTXAYB". The code uses dynamic programming to find LCS length.

2. Step 2: Trace the LCS calculation

   The LCS is "GTAB" with length 4. The code correctly computes this.

3. Step 3: Verify carefully

   Common subsequence: G T A B (positions match in order). Length is 4.

4. Final Answer:

   4 -> Option C

5. Quick Check:

   LCS length of "AGGTAB" and "GXTXAYB" = 4 [OK]

Hint: Trace matching chars in order, ignore gaps [OK]

Common Mistakes:

• Counting common characters not in order
• Confusing substring with subsequence
• Off-by-one errors in indexing

4. Identify the bug in the following Rust function that attempts to compute the LCS length:

fn lcs_length(s1: &str, s2: &str) -> usize {
    let m = s1.len();
    let n = s2.len();
    let mut dp = vec![vec![0; n]; m];
    for i in 1..m {
        for j in 1..n {
            if s1.as_bytes()[i] == s2.as_bytes()[j] {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = dp[i - 1][j].max(dp[i][j - 1]);
            }
        }
    }
    dp[m - 1][n - 1]
}

medium

A. The dp vector is initialized with size m x n instead of (m+1) x (n+1).

B. The loops start from 0 instead of 1, causing index errors.

C. The loops use 1..=m and 1..=n instead of 1..m and 1..n, causing out of bounds.

D. The function returns dp[m][n] which is out of bounds.

Solution

1. Step 1: Check dp vector initialization

   The dp vector is initialized as m x n, but it should be (m+1) x (n+1) to handle base cases and indexing from 1.

2. Step 2: Understand loop ranges and indexing

   Loops start from 1..

3. Final Answer:

   The dp vector is initialized with size m x n instead of (m+1) x (n+1). -> Option A

4. Quick Check:

   dp size must be (m+1) x (n+1) [OK]

Hint: dp table size must include extra row and column [OK]

Common Mistakes:

• Initializing dp with wrong size
• Incorrect loop ranges causing panic
• Wrong indexing of string bytes

5. Given two strings, write a Rust function that returns the actual Longest Common Subsequence string (not just length). Which approach below correctly reconstructs the LCS from the dp table?

hard

A. Start from dp[0][0], move right or down collecting characters whenever dp[i][j] increases.

B. Start from dp[m][n], move diagonally up-left if characters match, else move to the cell with the larger value, collecting matched characters in reverse order.

C. Traverse dp table row-wise and append characters when dp[i][j] is non-zero.

D. Reverse both strings and find LCS length, then reverse the result to get LCS string.

Solution

1. Step 1: Understand dp table usage for reconstruction

   The dp table stores lengths of LCS for substrings. To reconstruct, start from dp[m][n] and move backwards.

2. Step 2: Trace path to build LCS string

   If characters match at s1[i-1] and s2[j-1], move diagonally up-left and add character. Else move to cell with larger dp value (up or left).

3. Step 3: Reverse collected characters

   Since traversal is from end to start, collected characters must be reversed to get correct LCS.

4. Final Answer:

   Start from dp[m][n], move diagonally up-left if characters match, else move to the cell with the larger value, collecting matched characters in reverse order. -> Option B

5. Quick Check:

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

Hint: Backtrack dp from bottom-right, collect matches, then reverse [OK]

Common Mistakes:

• Starting reconstruction from top-left
• Not reversing collected characters
• Ignoring dp values when moving