PPractick

The problem

You're building the foundational engine behind the "changelog minimizer" and "plagiarism scanner" tools you've been extending in recent tickets — but stripped down to its core ask. Given two strings text1 and text2, you need to find the length of their longest common subsequence: the longest sequence of characters that appears in both strings in the same relative order, but not necessarily contiguously. This single primitive is the backbone that Edit Distance, SCS, Min Insert/Delete, and LPS all build on top of.

Function signature

int longestCommonSubsequence(string text1, string text2);

Test cases

text1	text2	Output	Explanation
"abcde"	"ace"	3	"ace" is a common subsequence of both
"abc"	"abc"	3	identical strings → LCS is the whole string
"abc"	"def"	0	no common characters at all
"abc"	""	0	LCS with empty string is always 0
""	""	0	trivial
"aggtab"	"gxtxayb"	4	"gtab" is the LCS
"bl"	"yby"	1	"b" is the only common subsequence

(This is the canonical LeetCode 1143 formulation — nearly every other problem in this set reduces down to this one.)

How interviewers phrase it

• "Given two strings, find the length of their longest common subsequence."
• "How similar are these two pieces of text, allowing for gaps but preserving order?"
• Frequently the opening problem in a sequence of DP-on-strings questions — expect immediate follow-ups chaining into Edit Distance, SCS, or LPS right after you solve this.

Clarifying questions to ask

1. Subsequence (order preserved, gaps allowed) or substring (contiguous)? — Always confirm explicitly; this single question prevents solving the wrong problem entirely.
2. Do you want just the length, or the actual subsequence string too?
3. Are text1 and text2 guaranteed non-empty?
4. Case-sensitive matching?
5. Expected input size — standard O(n·m) DP is expected; huge inputs might prompt a space-optimization follow-up.

Follow-ups to expect

1. "Can you print the actual LCS string, not just the length?"
2. "Can you optimize space?"
3. "How does this relate to Edit Distance / SCS / Min Insertions-Deletions?"
4. "What about Longest Palindromic Subsequence?"
5. "Can you solve this in less than O(n·m) time?"
6. "What if you need LCS across THREE strings?"

Related questions

• Print Longest Common Subsequence Hard
• Minimum insertions or deletions to convert string A to B Hard
• Shortest common supersequence Hard
• Longest common substring Hard
• Longest palindromic subsequence Hard
• Minimum insertions to make string palindrome Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in