DSAhardStrings~40m

The Plagiarist

Problem

You are a backend engineer at an online coding education platform. Your plagiarism detector needs to identify the longest repeated code snippet — the longest substring that appears at least twice in a given submission. Overlapping occurrences count.

Given a string s, return the longest substring that appears at least twice. If multiple substrings share the maximum length, return the lexicographically smallest one. If no repeated substring exists, return an empty string "".

Examples

Example 1

Input: "banana"

Output: "ana"

"ana" appears at index 1 and index 3 (overlapping). The suffix array sorts all suffixes and the LCP array finds the longest common prefix between adjacent sorted suffixes.

Example 2

Input: "aaaa"

Output: "aaa"

"aaa" appears at index 0 and index 1 — overlapping occurrences count. "aaa" is longer than "aa" or "a".

Example 3

Input: "abcabcabc"

Output: "abcabc"

"abcabc" appears at index 0 and index 3 (overlapping). Length beats frequency — "abc" appears 3 times but "abcabc" is longer.

Constraints

›1 <= len(s) <= 1000
›s contains only lowercase English letters

Loading question…