How should I practice Longest Duplicate Substring?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google phone screen problems in FastPrep.

Is Longest Duplicate Substring associated with Google?

FastPrep tags this as a Google phone screen coding practice problem when the problem catalog has that company and stage context.

Longest Duplicate Substring

Google● HardINTERNNEW GRADPHONE SCREEN

Learn

Problem statement

You are given a lowercase string s. A duplicate substring is a non-empty contiguous substring that occurs at least twice in s. The occurrences may overlap.

Return a duplicate substring of maximum length. If several different substrings have maximum length, return the lexicographically smallest one. Return an empty string if no duplicate substring exists.

Function

longestDuplicateSubstring(s: String) → String

Examples

Example 1

s = "banana"return = "ana"

ana occurs twice and no longer substring occurs at least twice.

Example 2

s = "abcd"return = ""

No non-empty substring appears twice.

Example 3

s = "aaaaa"return = "aaaa"

The two overlapping occurrences start at indices 0 and 1.

Constraints

2 <= s.length <= 30000.
s contains only lowercase English letters.