How to Solve: Longest Common Subsequence (LCS) – Complete Guide for FAANG Interviews

How to Solve: Longest Common Subsequence (LCS) – Complete Guide for FAANG Interviews

? Introduction

"This single problem type appears in 1 out of every 3 FAANG onsite interviews—master it, and you’ll prove you can break down complex string/DP problems with surgical precision."

? WHAT YOU NEED TO KNOW FIRST

Before tackling LCS, ensure you understand: 1. Dynamic Programming (DP) Basics – Memoization, tabulation, and state transitions. 2. String Manipulation – Substrings, subsequences, and character comparisons. 3. Recursion & Backtracking – How to decompose problems into smaller subproblems.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK (Mental Checklist)

1. Clarify the Problem
2. Confirm if it’s subsequence (order matters, not contiguous) vs. substring (contiguous).

3. Ask: "Can we assume ASCII or Unicode strings?" (Affects space complexity.)

4. Define the DP State

5. dp[i][j] = LCS of s1[0..i-1] and s2[0..j-1]

6. Base Case: dp[0][j] = 0 (empty string), dp[i][0] = 0 (empty string).

7. Write the Recurrence Relation

8. If s1[i-1] == s2[j-1] → dp[i][j] = dp[i-1][j-1] + 1

9. Else → dp[i][j] = max(dp[i-1][j], dp[i][j-1])

10. Choose DP Approach

11. Tabulation (Bottom-Up): Fill a 2D table iteratively (preferred for interviews).

12. Memoization (Top-Down): Recursive with caching (easier to explain but slower).

13. Optimize Space (If Needed)

14. Use two 1D arrays (prev and curr) instead of a full 2D table.

15. Reconstruct the LCS (If Required)

16. Start from dp[m][n] and backtrack to build the subsequence.

17. Edge Cases & Testing

18. Empty strings, identical strings, no common subsequence.

19. Test with s1 = "abc", s2 = "def" (LCS = "").

20. Time & Space Complexity

21. Time: O(mn) (where m, n = lengths of s1, s2).
22. Space: O(mn) → O(min(m, n)) with optimization.

? WORKED EXAMPLES

Example 1 – Basic LCS (Tabulation)

Problem: Find the length of the LCS of "abcde" and "ace".

Step-by-Step: 1. Initialize dp[m+1][n+1] (6x4 table, filled with 0s). 2. Fill the table:
- dp[1][1] = 1 (a == a)
- dp[2][2] = 1 (b != c)
- dp[3][3] = 2 (c == c)
- dp[5][3] = 3 (e == e) 3. Result: dp[5][3] = 3 (LCS = "ace").

Python Code:

def longestCommonSubsequence(s1: str, s2: str) -> int:

    m, n = len(s1), len(s2)

    dp = [[0]  (n + 1) for _ in range(m + 1)]


    for i in range(1, m + 1):

        for j in range(1, n + 1):

            if s1[i-1] == s2[j-1]:

                dp[i][j] = dp[i-1][j-1] + 1

            else:

                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    return dp[m][n]

Complexity: - Time: O(mn) - Space: O(mn) → Can be optimized to O(n).

Why This Works: - The DP table tracks the LCS length for all prefixes of s1 and s2. - The recurrence relation ensures we either extend the LCS (if characters match) or take the best of the two previous states.

Example 2 – Medium (Space Optimization)

Problem: Find the LCS length with O(n) space.

Approach: - Use two 1D arrays (prev and curr) instead of a full 2D table.

Python Code:

def longestCommonSubsequence(s1: str, s2: str) -> int:

    m, n = len(s1), len(s2)

    prev = [0]  (n + 1)


    for i in range(1, m + 1):

        curr = [0]  (n + 1)

        for j in range(1, n + 1):

            if s1[i-1] == s2[j-1]:

                curr[j] = prev[j-1] + 1

            else:

                curr[j] = max(prev[j], curr[j-1])

        prev = curr

    return prev[n]

Complexity: - Time: O(mn) - Space: O(n)

Why This Works: - We only need the previous row to compute the current row, reducing space.

Example 3 – Hard (Reconstruct the LCS)

Problem: Return the actual LCS string, not just its length.

Approach: 1. Compute the DP table as before. 2. Backtrack from dp[m][n] to build the LCS.

Python Code:

def longestCommonSubsequence(s1: str, s2: str) -> str:

    m, n = len(s1), len(s2)

    dp = [[0]  (n + 1) for _ in range(m + 1)]


    for i in range(1, m + 1):

        for j in range(1, n + 1):

            if s1[i-1] == s2[j-1]:

                dp[i][j] = dp[i-1][j-1] + 1

            else:

                dp[i][j] = max(dp[i-1][j], dp[i][j-1])


    # Backtrack to reconstruct LCS

    i, j = m, n

    lcs = []

    while i > 0 and j > 0:

        if s1[i-1] == s2[j-1]:

            lcs.append(s1[i-1])

            i -= 1

            j -= 1

        elif dp[i-1][j] > dp[i][j-1]:

            i -= 1

        else:

            j -= 1

    return ''.join(reversed(lcs))

Complexity: - Time: O(mn) - Space: O(mn)

Why This Works: - The backtracking step follows the DP table to reconstruct the LCS by moving diagonally when characters match.

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap (Closing Script)

"Alright, let’s lock this in. The Longest Common Subsequence problem is a DP classic—you’ll see it in Google, Meta, and Amazon interviews because it tests your ability to break down string problems with precision.

Here’s your 30-second cheat sheet: 1. Define dp[i][j] as the LCS of s1[0..i-1] and s2[0..j-1]. 2. Fill the table with dp[i][j] = dp[i-1][j-1] + 1 if characters match, else max(dp[i-1][j], dp[i][j-1]). 3. Optimize space with two 1D arrays if needed. 4. Reconstruct the LCS by backtracking from dp[m][n].

Edge cases? Empty strings, identical strings, no common subsequence. Time complexity? O(mn). Space? O(mn) → O(n) with optimization.

Now go crush that interview. You’ve got this!

? Final Notes

• Practice: Solve LCS on LeetCode (Problems 1143, 583, 712).
• Follow-ups: Be ready for variants (e.g., minimum deletions to make strings equal).
• Whiteboard: Draw the DP table first—interviewers love it!

Good luck! ?