1086. Longest Shared Piece
Two researchers each sequenced a strand of DNA-like data, written as lowercase strings a and b. To judge how related the strands are, they want the longest block of consecutive letters that appears in both strings.
Return the length of the longest string that is a contiguous substring of a and a contiguous substring of b. The block may start at different positions in the two strings. If the strings have no letter in common, return 0.
Only the length is requested, not the block itself. Filling a table that compares every position of a with every position of b is too slow for the largest inputs.
Example 1
- Input:
- a = "xabcdey", b = "zabcdeq"
- Output:
- 5
- Explanation:
The longest block of letters that both strings contain contiguously is "abcde", five letters long.
Example 2
- Input:
- a = "banana", b = "ananas"
- Output:
- 5
- Explanation:
"anana" sits at positions 1 to 5 of the first string and positions 0 to 4 of the second string.
Example 3
- Input:
- a = "abc", b = "xyz"
- Output:
- 0
- Explanation:
The strings share no letter at all, so the longest shared piece is empty and the answer is 0.
Constraints
1 ≤ a.length, b.length ≤ 40000
Both strings consist of lowercase English letters
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,800 msC++ 700 msJava 1,400 msJavaScript 1,400 msTypeScript 1,400 ms
Expected complexity
- Time
- O((n + m) log(min(n, m)))
- Space
- O(n + m)