Practice/Amazon/Leetcode 1044. Longest Duplicate Substring

Leetcode 1044. Longest Duplicate Substring

CodingMust

Problem

Given a string consisting of lowercase English letters, find the longest substring that appears at least twice in the string. The occurrences of this substring are allowed to overlap.

If no such substring exists, return an empty string.

Requirements

1. Return the longest substring that appears at least twice in the input string
2. Overlapping occurrences are permitted
3. If multiple substrings of the same maximum length exist, return any one of them
4. Return an empty string if no duplicate substring exists

Constraints

• 2 ≤ s.length ≤ 30,000
• s consists only of lowercase English letters ('a' to 'z')
• Time complexity should be better than O(n³)
• Space complexity should be reasonable for the given input size

Examples

Example 1:

Input: s = "banana" Output: "ana" Explanation: The substring "ana" appears twice: at index 1 ("b[ana]na") and index 3 ("ban[ana]")

Example 2:

Input: s = "abcd" Output: "" Explanation: No substring appears more than once

Example 3:

Input: s = "aabcaab" Output: "aab" Explanation: The substring "aab" appears at index 0 and index 4