mediumDSA

How do you find the longest common subsequence?

Q: How do you find the longest common subsequence?

**Intuition.** A subsequence keeps order but can skip characters. The LCS of two strings is found with a **2-D DP table**: dp[i][j] = LCS length of the first i chars of A and first j of B. If the current characters match, extend the diagonal; otherwise take the best of dropping one character from either string. A="ABCBDAB", B="BDCAB" → LCS length 4 match → dp[i-1][j-1] + 1 (diagonal) mismatch → max(up, left)

363 views

Understand the problem

Explain LCS.

dplcs

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Stuck? AI Nudge Available

Get a conceptual hint to guide your logic without spoiling the final implementation.

Study the solution

The solution is waiting

Give it an honest attempt first — then compare your thinking with the full walkthrough.

Read the code

LCS length (2-D DP)

Run Playground

def lcs(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i-1] == b[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]


# --- demo ---
print(lcs("ABCBDAB", "BDCAB"))   # 4  (e.g. "BCAB")

Join the discussion

Discussion (0)

No responses yet. Be the first to share what you think.

How do you solve the coin change problem?

How do you find a peak element in an array?