PPractick

The problem

You're building a "near-duplicate detector" for a code-plagiarism scanner. Unlike the earlier LCS-family problems where matches could be scattered non-contiguously, here you specifically want to detect copy-pasted contiguous blocks of code between two submissions str1 and str2 — since a plagiarized chunk is, by definition, an unbroken run of matching characters, not just any matching subsequence. Given two strings, find the length of the longest common substring (contiguous in both strings).

Function signature

int longestCommonSubstring(string str1, string str2);

Test cases

str1	str2	Output	Explanation
"abcde"	"abfce"	2	"ab" is the longest contiguous common substring
"abcdxyz"	"xyzabcd"	4	"abcd" (or "xyz") — longest contiguous match is length 4
"zxabcdezy"	"yzabcdezx"	6	"abcdez" is common and contiguous in both
"abc"	"abc"	3	identical strings
"abc"	"def"	0	no common characters at all
""	"abc"	0	empty string has no substrings
"aaaa"	"aa"	2	longest run of matching contiguous "a"s is 2 (bounded by shorter string)

(Key contrast to flag immediately: this is NOT the same as Longest Common Subsequence — "abcde" vs "abfce" have LCS length 4 ("abce"), but longest common SUBSTRING is only 2 ("ab"). Interviewers love testing whether you conflate these two.)

How interviewers phrase it

• "Given two strings, find the length of their longest common substring."
• "Find the longest contiguous block of characters shared by both strings."
• Frequently asked as a direct follow-up right after LCS, specifically to test whether you notice the subtle but critical difference between "subsequence" and "substring."

Clarifying questions to ask

1. Substring (contiguous) or subsequence (order-preserved, not necessarily contiguous)? — Always confirm explicitly, since the two problems sound similar but need entirely different DP transitions.
2. Do you want just the length, or the actual substring itself?
3. If multiple substrings of the same maximum length exist, does it matter which one I report (for reconstruction)?
4. Case-sensitive matching?
5. Expected input sizes — O(n·m) DP is standard/expected; for very large inputs they might want to hear about suffix-automaton or suffix-array based O(n+m) approaches as a stretch follow-up.

Follow-ups to expect

1. "How is this different from Longest Common Subsequence?"
2. "Can you reconstruct the actual substring, not just the length?"
3. "Can you optimize space?"
4. "Can you solve this in O(n + m) instead of O(n·m)?"
5. "What if you needed the longest common substring among K strings, not just 2?"
6. "What if the substrings must also be palindromes?"

Related questions

• 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