Solving LeetCode 1143: Longest Common Subsequence — An Intuitive Guide For Beginner

In this article, we’ll solve **LeetCode problem 1143: Longest Common Subsequence. **What make this article be different:

beginner friendly, fix confusion, avoid traps

LeetCode 1143 asks:

Given two strings text1 and text2, return the length of their Longest Common Subsequence (LCS).

A subsequence means you can delete characters without changing the relative order. Example: “abcde” and “ace” → LCS length = 3 (“ace”).

This problem is basically: “Walk through both strings and make the best choices without getting lost.”

OUTLINE

1. Step by Step Code Implementation 2. Common Traps (and Fixes) 3. Common Confusions (and Fixes) 4. Edge Cases

1. Code Implementation (Python)

At any moment, you are standing at:

• index i in text1
• index j in text2

Define:

dfs(i, j) = the LCS length between text1[i:] and text2[j:]

What does (i, j) represent?

• i = current index in text1
• j = current index in text2

So (i, j) uniquely defines:

The best LCS we can build starting from here.

So we have to return dfs(0, 0) → the best LCS we can build starting from (0,0)

Step 1 — Base case (when the game ends)

If either pointer reaches the end, there’s nothing left to match:

# base case
if i == len(text1) or j == len(text2) → return 0

Step 2 — If characters match, take it

If text1[i] == text2[j], that character can be part of the subsequence.

So:

• we count it → 1
• and move both pointers forward → dfs(i+1, j+1)

if text1[i] == text2[j]:
    return 1 + dfs(i + 1, j + 1) # A match. Count it in and move on.

Step 3 — If characters don’t match, we must “skip” something

If text1[i] != text2[j], we can’t take both at the same time.

So we try both possibilities and PICK THE BEST (max):

• skip text1[i] → dfs(i+1, j)
• skip text2[j] → dfs(i, j+1)
• pick the best

return max(dfs(i + 1, j), dfs(i, j + 1))

Step 4 — Putting it together

def longestCommonSubsequence(self, text1: str, text2: str) -> int:

    def dfs(i, j):
        if i == len(text1) or j == len(text2):
            return 0              ✅ # 1. case: either pointer reach the end

        if text1[i] == text2[j]:        ✅ # 2. case: character match
            return 1 + dfs(i + 1, j + 1)   # count & move both pointer 

        return max(dfs(i + 1, j), dfs(i, j + 1))
               ✅ # 3. case: characters don't match

    return dfs(0, 0)

# This is naive solution

Time Complexity

Let:

• m = len(text1)
• n = len(text2)

In the worst case (few matches), each state branches into 2 calls: O(2^(m+n)) (exponential)

Space Complexity

recursion depth up to m + n → O(m + n) (call stack)

🚨 Warning

Despite intuitive, this naive solution times out: the hidden repetition. The recursion keeps recomputing the same states (i, j) again and again.

Example: dfs(3, 5) might be reached from:

• dfs(2,5) → skip text1
• dfs(3,4) → skip text2

and many other paths

So you’re solving the same subproblem repeatedly.

This is the classic sign that the problem is Dynamic Programming (DP).

✅ Fix: Memoization (same idea + remember answers)

We keep a cache:

• key = (i, j)
• value = dfs(i, j)

If we’ve computed it once, we reuse it.

def longestCommonSubsequence(self, text1: str, text2: str) -> int:
    memo = {}                   ✅ # add a memo dictionary

    def dfs(i, j):
        if i == len(text1) or j == len(text2):
            return 0

         if (i, j) in memo:      
             return memo[(i, j)]    

        if text1[i] == text2[j]:
            memo[(i, j)] = 1 + dfs(i + 1, j + 1)
        else:
            memo[(i, j)] = max(dfs(i + 1, j), dfs(i, j + 1))

        return memo[(i, j)]

    return dfs(0, 0)

# This is optimized solution

Time Complexity

• There are only m * n unique states (i, j).
• Each state is computed once, and work inside is O(1), so: O(m * n)

Space Complexity

• O(m * n) for memo
• plus O(m + n) call stack
• Overall: O(m * n) dominates

2. Common Traps (and fixes)

❌ Trap 1: “Subsequence” vs “Substring”

• Substring = continuous chunk
• Subsequence = can skip characters

✅ Fix: Repeat this rule:

LCS allows skipping; order must remain.

❌ Trap 2: Returning 1 + max(…) on mismatch

Some beginners do:

return 1 + max(dfs(i+1,j), dfs(i,j+1))

# ❌ incorrect

That’s wrong because mismatch does not add a matched character.

✅ Fix: only add +1 when text1[i] == text2[j]

return max(dfs(i+1,j), dfs(i,j+1))

# ✅ Correct

Any other traps you know ?

Comment down below ⬇️ ⬇️ ⬇️

3. Common Beginner Confusion (and Fix)

❌ Confusion 1:

“Why do we try both skips?”

✅ Answer: Because when text1[i] != text2[j], you don’t know which character is “blocking” the best subsequence.

• Skipping text1[i] might reveal a match later.
• Skipping text2[j] might reveal a different match later.

FIX mental model: when mismatch happens, you’re choosing which string to “advance” to find a better alignment.

❌ Confusion 2:

“Why does memoization make it O(mn)?”*

✅ Answer: Because (i, j) fully describes the remaining problem: text1[i:] and text2[j:].

There are only:

• m possible i
• n possible j

so m*n possible states

DP is just “don’t solve the same state twice.”

❌ Confusion 3:

“What does dfs(i, j) actually represent?”

✅ Answer:

• It’s NOT “the answer so far”.
• It’s “the best answer you can still achieve from here”.

✅ FIX phrase:

dfs(i, j) = best LCS length for the suffixes starting at i and j.

Do you have any other confusions? Just comment down below ⬇️⬇️⬇️

4. Edge Case Handling

Even though the logic is clean, interviewers love edge cases, like below:

• One or both string are empty
• Identical strings
• No characters match at all
• One string is much longer than the other
• Repeated characters

Other possible edge cases in mind?

Let’s discuss on the comment section ⬇️⬇️⬇️

Let’s go through them carefully.

Edge Case 1 — One or both string are empty

Example:

text1 = ""
text2 = "abc"

or

text1 = ""
text2 = ""

Does our solution handle this?

Yes, because:

if i == len(text1) or j == len(text2): return 0

If text1 is empty, len(text1) == 0, so dfs(0, 0) immediately returns 0.

✅ No special handling needed.

Edge Case 2 — Identical strings

Example:

text1 = "abcde"
text2 = "abcde"

Expected result: 5

Does our solution handle this?

Every character matches, we always go into:

return 1 + dfs(i+1, j+1)

So it walks diagonally until the end.

✅ Works perfectly.

Edge Case 3 — No characters match at all

Example:

text1 = "abc"
text2 = "xyz"

Expected result: 0

Does our solution handle this?

Every comparison is mismatch, so we keep exploring:

max(dfs(i+1, j), dfs(i, j+1))

Eventually all paths hit base case and return 0.

✅ Correct output = 0

Edge Case 4 — One string is much longer than the other

Example:

text1 = "aaaaaaaaaa"
text2 = "aa"

Expected result: 2

Even though text1 has many “a”s, text2 only has two.

Does our solution handle this?

The recursion ensures we can only count matches when both pointers move.

So we cannot “overcount” characters.

The structure:

Match → move both pointers

Mismatch → explore skipping

ensures correctness.

✅ Safe.

Edge Case 5— Repeated Characters

Example:

text1 = "abcba"
text2 = "abcbcba"

Beginners sometimes worry:

“Will it accidentally reuse the same character twice?”

Answer: No.

Because each recursive call strictly moves forward in indices:

• i never decreases
• j never decreases

So each character position can only be used once.

That’s guaranteed by how we define the state (i, j).

✅ No duplication possible.

Thanks for reading! Hopefully you got the core idea.

Comments down ⬇️ below️️ if you have any questions. I will be glad to reply to every questions.

Let’s stay in touch:

🔗 Medium: Follow → Eka Gunawan

🔗 LinkedIn: Connect for career and job strategy → [linkedin.com/in/eka-gun-tw/]

Found this helpful? Give it a clap and follow for more algorithm deep-dives!