Longest Shared Fragment
Problem
A plagiarism checker compares two texts first and second. A fragment is a contiguous block of characters.
Return the length of the longest fragment that appears in both texts, or 0 if they have no character in common.
Example 1
- Input:
- first = "unhappiness", second = "happening"
- Output:
- 4
"happ" occurs in both. "happe" does not, because "unhappiness" continues with "i".
Example 2
- Input:
- first = "abc", second = "xyz"
- Output:
- 0
Constraints
- 0 ≤ first.length, second.length ≤ 2000
- Both strings contain lowercase English letters only.
Hint
Show the first hint
Anchor the fragment at its end: how long is the longest shared fragment ending exactly at first[i - 1] and second[j - 1]?
Walkthrough
How to approach it
01Clarify before coding
- Fragment means contiguous? Yes, unlike a subsequence.
- Return the length only? Yes.
- Is the comparison case-sensitive? Only lowercase letters appear, so it does not matter.
02Brute force
For every start pair (i, j), extend while characters match and keep the longest run.
Cost: O(m · n · min(m, n)) in the worst case (e.g. long runs of the same letter): about 8 · 10^9 for 2000 × 2000.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.