903. Border Prefix
A weaver's pattern code is a string s. A border of the code is a non-empty piece that appears both at the very start and at the very end of the code, where the piece is shorter than the whole code (the two copies may overlap each other).
Return the longest border of s. If the code has no border, return the empty string.
Aim for time O(n) where n is the length of s; comparing every candidate length character by character is O(n^2) and will be too slow.
Example 1
- Input:
- s = "quokkaquokka"
- Output:
- "quokka"
- Explanation:
The first six letters 'quokka' equal the last six letters, and no longer proper prefix is also a suffix.
Example 2
- Input:
- s = "zebrazebraz"
- Output:
- "zebraz"
- Explanation:
The suffix 'zebraz' equals the prefix 'zebraz' (they overlap in the middle), so that is the longest border.
Example 3
- Input:
- s = "plumber"
- Output:
- ""
- Explanation:
No proper prefix reappears at the end, so the answer is the empty string.
Constraints
1 ≤ s.length ≤ 105
s contains only lowercase English letters.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)