DiffPush Tier Strings Hard · Hard O(n) · O(n)
A music engraver examines a melody line for its longest opening phrase that also closes the piece — a non-empty phrase that starts and ends the score without being the whole score. Finding it lets the engraver compress the notation. When no such phrase exists, the report comes back empty.
Input: A string s.
Output: Return the longest non-empty proper prefix of s that is also a suffix of s, or "" when none exists.
1 <= len(s) <= 10^5s contains only lowercase English lettersInput: {"s":"level"}
Output: "l"
"l" opens and closes the word; no longer proper prefix repeats as a suffix.
Input: {"s":"ababab"}
Output: "abab"
"abab" is both the opening and the closing phrase of the period-2 melody.