Longest Common Subsequence

📋

Longest Common Subsequence

Edge cases:

</>

IDE

def lcs(text1: str, text2: str, i: int, j: int) -> int:public int lcs(String text1, String text2, int i, int j)int lcs(const string &text1, const string &text2, int i, int j)function lcs(text1, text2, i, j)

def lcs(text1, text2, i, j):
    # Write your solution here
    pass

class Solution {
    public int lcs(String text1, String text2, int i, int j) {
        // Write your solution here
        return 0;
    }
}

#include <string>
using namespace std;

int lcs(const string &text1, const string &text2, int i, int j) {
    // Write your solution here
    return 0;
}

function lcs(text1, text2, i, j) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Missing base case for empty strings or incorrect initialization.✅ Add base case: if i == 0 or j == 0, return 0 immediately.

Wrong: 2 for input ("abc", "abcbc")Counting characters multiple times as if unbounded usage allowed.✅ Ensure DP indices represent prefixes and do not reuse characters beyond their position.

Wrong: 5 for input ("abcde", "edcba")Greedy approach matching characters out of order.✅ Use DP to consider all subsequence possibilities, not greedy matching.

Wrong: 1 for input ("aaa", "aa")Incorrect handling of repeated characters, undercounting LCS length.✅ Use DP max transitions to correctly count repeated characters.

Wrong: TLE on large inputsUsing brute force exponential recursion without memoization or DP.✅ Implement bottom-up or top-down DP with memoization to achieve O(m*n) time.

✓

Test Cases

Focus on handling base cases and minimal inputs correctly.

Think about tricky cases that break greedy or naive logic.

Optimize your solution to run efficiently on large inputs.

t1_01basic

Input{"text1":"abcde","text2":"ace","i":5,"j":3}

Expected3

⏱ Performance - must finish in 2000ms

The longest common subsequence is "ace" and its length is 3.

💡 Think about comparing characters from the end of both strings.

💡 Use dynamic programming to store results of subproblems for indices i and j.

💡 If characters match, add 1 plus result from i-1 and j-1; else max of i-1,j and i,j-1.

Why it failed: Returned incorrect length for canonical example; likely missed adding 1 when characters match. Fix by adding 1 + lcs(i-1, j-1) when text1[i-1] == text2[j-1].

✓ Correctly computed LCS length for canonical example.

t1_02basic

Input{"text1":"abc","text2":"abc","i":3,"j":3}

Expected3

⏱ Performance - must finish in 2000ms

Both strings are identical, so the LCS is the entire string with length 3.

💡 Check if characters at current indices are equal.

💡 If equal, increment count and move diagonally in DP table.

💡 If not equal, take max of left and top cells in DP table.

Why it failed: Failed to handle identical strings correctly; possibly returning less than full length. Fix by ensuring matching characters increment LCS count.

✓ Correctly handled identical strings returning full length.

t2_01edge

Input{"text1":"","text2":"abc","i":0,"j":3}

Expected0

⏱ Performance - must finish in 2000ms

One string is empty, so no common subsequence exists; output is 0.

💡 Consider base cases when either string length is zero.

💡 Return 0 immediately if i == 0 or j == 0.

💡 Ensure recursion or DP handles empty strings correctly.

Why it failed: Did not return 0 for empty string input; fix by adding base case returning 0 when i==0 or j==0.

✓ Correctly returns 0 when one string is empty.

t2_02edge

Input{"text1":"a","text2":"b","i":1,"j":1}

Expected0

⏱ Performance - must finish in 2000ms

Single character strings with no common characters have LCS length 0.

💡 Check if single characters match.

💡 If not matching, result should be 0 for single character strings.

💡 Return max of lcs(i-1, j) and lcs(i, j-1) which are zero here.

Why it failed: Incorrectly returned non-zero for no common single characters; fix by ensuring no increment when characters differ.

✓ Correctly returns 0 for single character strings with no match.

t2_03edge

Input{"text1":"a","text2":"a","i":1,"j":1}

Expected1

⏱ Performance - must finish in 2000ms

Single character strings that match have LCS length 1.

💡 Check if characters at i-1 and j-1 are equal.

💡 If equal, return 1 plus lcs(i-1, j-1) which is 0 here.

💡 Ensure base case returns 0 for zero indices.

Why it failed: Failed to return 1 for matching single characters; fix by adding 1 when characters match.

✓ Correctly returns 1 for matching single character strings.

t2_04edge

Input{"text1":"xyz","text2":"abc","i":3,"j":3}

Expected0

⏱ Performance - must finish in 2000ms

Strings with no common characters have LCS length 0.

💡 Check all characters for matches.

💡 If no characters match, result is 0.

💡 DP should return 0 when no subsequence exists.

Why it failed: Incorrectly returns non-zero for strings with no common characters; fix by ensuring no increment when characters differ.

✓ Correctly returns 0 for strings with no common characters.

t3_01corner

Input{"text1":"abcde","text2":"edcba","i":5,"j":5}

Expected1

⏱ Performance - must finish in 2000ms

Strings have all characters reversed; only one character can match in subsequence.

💡 Greedy approach picking first matching character fails here.

💡 Check all subsequence possibilities, not just first matches.

💡 Use DP to consider all pairs, not greedy matching.

Why it failed: Greedy approach overcounts matches; fix by using DP to consider all subsequence options.

✓ Correctly handles reversed strings with LCS length 1.

t3_02corner

Input{"text1":"aaa","text2":"aa","i":3,"j":2}

Expected2

⏱ Performance - must finish in 2000ms

Repeated characters require careful counting; LCS length is 2.

💡 Avoid counting same character multiple times incorrectly.

💡 DP must handle repeated characters by proper state transitions.

💡 Ensure max of excluding one character at a time is taken.

Why it failed: Incorrectly counts repeated characters multiple times; fix by proper DP state transitions and max comparisons.

✓ Correctly counts repeated characters in LCS.

t3_03corner

Input{"text1":"abc","text2":"abcbc","i":3,"j":5}

Expected3

⏱ Performance - must finish in 2000ms

Tests confusion between 0/1 knapsack and unbounded; characters can be used once only.

💡 Each character can be matched at most once in subsequence.

💡 Do not count multiple occurrences of same character in text2 beyond their position.

💡 DP indices represent prefixes, not unlimited reuse.

Why it failed: Mistakenly counts characters multiple times (unbounded); fix by indexing DP properly to avoid reuse.

✓ Correctly enforces 0/1 usage of characters in subsequence.

t4_01performance

Input{"text1":"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","text2":"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","i":100,"j":100}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, O(m*n) DP expected to complete within 2 seconds.

💡 Brute force exponential solutions will time out here.

💡 Use bottom-up DP with O(m*n) time complexity.

💡 Consider space optimization if memory is a concern.

Why it failed: TLE due to exponential or inefficient approach; fix by implementing O(m*n) DP solution.

✓ Efficient DP solution confirmed by passing performance test.

Practice

1. Consider the following Python code that counts palindromic substrings using the expand around center approach. What is the final returned count when the input string is "aaa"?

def countSubstrings(s: str) -> int:
    n = len(s)
    count = 0

    def expand(left, right):
        nonlocal count
        while left >= 0 and right < n and s[left] == s[right]:
            count += 1
            left -= 1
            right += 1

    for i in range(n):
        expand(i, i)      # Odd length palindromes
        expand(i, i + 1)  # Even length palindromes

    return count

print(countSubstrings('aaa'))  # ?

easy

A. 3

B. 6

C. 4

D. 5

Solution

1. Step 1: Trace expansions for i=0

   expand(0,0) counts 'a' -> count=1; expand(0,1) counts 'aa' -> count=2

2. Step 2: Trace expansions for i=1 and i=2

   i=1: expand(1,1) counts 'a', 'aaa' -> +2; expand(1,2) counts 'aa' -> +1; i=2: expand(2,2) counts 'a' -> +1; total count=6

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   All palindromic substrings: 'a', 'a', 'a', 'aa', 'aa', 'aaa' [OK]

Hint: Count includes all odd and even length palindromes [OK]

Common Mistakes:

• Counting only single characters or missing even length palindromes

2. You are given two strings and want to find the length of the longest substring that appears in both strings contiguously. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Longest Common Subsequence DP approach that allows skipping characters

B. Greedy approach that extends matching characters until a mismatch occurs

C. Dynamic Programming that builds a 2D table tracking lengths of matching suffixes

D. Sorting all substrings of both strings and finding the longest common prefix

Solution

1. Step 1: Understand problem requires contiguous matching substrings

   Longest Common Substring requires contiguous characters, so subsequence approaches that allow gaps won't work.

2. Step 2: Identify DP approach tracking matching suffix lengths

   Dynamic Programming with a 2D table (or optimized 1D) that stores lengths of matching suffixes at each index pair guarantees optimal solution.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Only DP tracking contiguous matches solves this optimally [OK]

Hint: Longest common substring requires contiguous DP, not subsequence [OK]

Common Mistakes:

• Confusing substring with subsequence
• Trying greedy extension only
• Sorting substrings is inefficient

3. Consider the following code snippet for finding the longest palindromic substring using dynamic programming. What is the value of max_len after processing the input s = "abba"?

easy

A. 1

B. 3

C. 2

D. 4

Solution

1. Step 1: Trace dp for input "abba"

   Single chars dp[i][i] = True, max_len=1. For length=2, "ab" dp[0][1]=False, "bb" dp[1][2]=True, max_len=2. For length=3, "abb" dp[0][2]=False, "bba" dp[1][3]=False. For length=4, "abba" dp[0][3]=True (since s[0]==s[3] and dp[1][2]=True), max_len=4.

2. Step 2: Confirm max_len update

   max_len updated to 2 at "bb", then to 4 at "abba".

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Longest palindrome is "abba" length 4 [OK]

Hint: Check dp updates for length 4 substring "abba" [OK]

Common Mistakes:

• Off-by-one errors in length calculation
• Missing even length palindrome updates
• Confusing max_len update condition

4. Consider the following Python code implementing the space-optimized DP solution for maximum uncrossed lines. What is the value of dp after the outer loop completes for i=2 when nums1 = [1,4,2] and nums2 = [1,2,4]?

easy

A. [0, 1, 2, 2]

B. [0, 1, 1, 1]

C. [0, 1, 1, 2]

D. [0, 0, 1, 1]

Solution

1. Step 1: Trace dp after i=1

   For i=1 (nums1[0]=1), dp updates to [0,1,1,1] because nums2 has 1 at j=1, matches increment dp[1].

2. Step 2: Trace dp after i=2

   For i=2 (nums1[1]=4), dp updates as follows: - j=1: no match, dp[1]=max(dp[1], dp[0])=1 - j=2: no match, dp[2]=max(dp[2], dp[1])=1 - j=3: match (4==4), dp[3]=prev+1=1+1=2 where prev is dp[2] before update which was 1, so dp after i=2 is [0,1,1,2].

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Matches at positions (1,1) and (2,3) give dp[3]=2 after i=2 [OK]

Hint: Track prev and dp[j] carefully to avoid off-by-one errors [OK]

Common Mistakes:

• Confusing prev and dp[j] updates
• Off-by-one indexing in dp array

5. Suppose the problem is modified so that characters can be deleted multiple times (i.e., you can reuse characters from s1 and s2 any number of times) to minimize the ASCII delete sum to make the strings equal. Which of the following approaches correctly adapts the solution?

hard

A. Use the same DP but allow transitions to reuse characters by not advancing indices when characters match

B. Use a greedy approach deleting characters with the highest ASCII values first until strings match

C. Apply the original DP without changes since reuse does not affect the minimum delete sum

D. Modify the DP to consider infinite reuse by converting it into an unbounded knapsack style problem with nested loops over characters

Solution

1. Step 1: Understand reuse changes problem nature

   Allowing reuse means characters can be matched multiple times, similar to unbounded knapsack.

2. Step 2: Adapt DP accordingly

   DP must allow multiple uses of characters, requiring nested loops to consider all reuse possibilities, unlike original one-to-one matching.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Unbounded knapsack analogy fits reuse scenario [OK]

Hint: Reuse means unbounded knapsack style DP needed [OK]

Common Mistakes:

• Assuming original DP works unchanged with reuse