190. Longest Mirror Inside
Inside a string s you want to find a stretch of consecutive characters that reads the same forwards and backwards, such a stretch is called a mirror. Return a longest mirror that occurs in s as a substring.
If several mirrors share the greatest length, return the one that starts earliest in s, so every input has exactly one correct answer. A single character is a mirror, so a non-empty string always has an answer. Growing a mirror outwards from each of the 2n - 1 possible centres solves the task in quadratic time, while testing all substrings one by one needs cubic time and is too slow.
Example 1
- Input:
- s = "qabbac"
- Output:
- "abba"
- Explanation:
The substring abba is a mirror of length 4, and nothing longer exists; the answer is abba.
Example 2
- Input:
- s = "xyz"
- Output:
- "x"
- Explanation:
No two neighbouring characters match, so any single letter is a longest mirror; x, y and z are all accepted.
Constraints
1 ≤ s.length ≤ 2000
s contains only lower case 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 4,000 msC++ 1,000 msJava 2,000 msJavaScript 2,000 msTypeScript 2,000 ms
Expected complexity
- Time
- O(n^2)
- Space
- O(1)