How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Find longest duplicated substring | Google Coding Question

Q: Find longest duplicated substring

This question evaluates proficiency in string algorithms, pattern matching, and algorithmic complexity analysis, focusing on designing efficient data structures and algorithms for finding repeated substrings.

Find longest duplicated substring

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are given a string `s` consisting of lowercase English letters. A **substring** of `s` is any contiguous sequence of characters, i.e., `s[i..j)` for `0 ≤ i < j ≤ len(s)`. Design an algorithm to find **any one** of the longest substrings that appears **at least twice** in `s`. The two occurrences may overlap. If no substring appears at least twice, return the empty string. ### Requirements - Input: a string `s` of length `n` (e.g., `1 ≤ n ≤ 2 × 10^5`). - Output: a string representing one of the longest duplicated substrings. - Aim for an algorithm substantially better than the naive `O(n^2)` substring comparison approach. ### Examples - `s = "banana"` - Possible duplicated substrings: "a", "an", "ana" - Longest length is 3 ("ana"), so acceptable outputs include `"ana"`. - `s = "abcd"` - No duplicated substring, so output should be `""` (empty string). Describe your algorithm, its time and space complexity, and how it scales for large `n`.

Quick Answer: This question evaluates proficiency in string algorithms, pattern matching, and algorithmic complexity analysis, focusing on designing efficient data structures and algorithms for finding repeated substrings.

You are given a string s consisting of lowercase English letters. A substring is any contiguous non-empty sequence of characters in s. Return any one of the longest substrings that appears at least twice in s. The two occurrences may overlap. If no non-empty substring appears at least twice, return the empty string. Your algorithm should be substantially better than comparing all pairs of substrings naively.

Constraints

1 <= len(s) <= 2 * 10^5
s consists only of lowercase English letters
Overlapping occurrences are allowed

Examples

Input: ('banana',)

Expected Output: 'ana'

Explanation: 'ana' appears twice: at indices 1..3 and 3..5. No duplicated substring of length 4 exists.

Input: ('abcd',)

Expected Output: ''

Explanation: Every non-empty substring appears only once.

Input: ('aaaaa',)

Expected Output: 'aaaa'

Explanation: 'aaaa' appears twice with overlapping occurrences: indices 0..3 and 1..4.

Input: ('z',)

Expected Output: ''

Explanation: A single-character string has no substring that appears at least twice.

Input: ('mississippi',)

Expected Output: 'issi'

Explanation: 'issi' appears at indices 1..4 and 4..7, and no longer duplicated substring exists.

Input: ('abcabxabcd',)

Expected Output: 'abc'

Explanation: 'abc' appears at indices 0..2 and 6..8. No duplicated substring of length 4 exists.

Hints

All duplicated substrings can be represented compactly using a suffix-based structure such as a suffix array or suffix automaton.
In a suffix automaton, each state represents substrings with the same set of ending positions. If a state is reached by at least two end positions, the longest substring represented by that state is duplicated.

Quick Overview

This question evaluates proficiency in string algorithms, pattern matching, and algorithmic complexity analysis, focusing on designing efficient data structures and algorithms for finding repeated substrings.