Shortest Mirror by Prepending
HardTries & Strings
Problem
You may only add characters to the front of a string s. Return the shortest string you can obtain this way that is a palindrome.
Example 1
- Input:
- s = "race"
- Output:
- "ecarace"
The longest palindromic prefix is "r"; prepending the reverse of "ace" gives "ecarace".
Example 2
- Input:
- s = "abaab"
- Output:
- "baabaab"
"aba" is the longest palindromic prefix, so only "ba" is added.
Example 3
- Input:
- s = ""
- Output:
- ""
Constraints
- 0 ≤ s.length ≤ 5·10^4
- Lowercase English letters only.
Hint
Show the first hint
Whatever you prepend must mirror some tail of s. Which part of s can stay unmatched by added characters?
Walkthrough
How to approach it
01Clarify before coding
- Only prepending is allowed? Yes, no deletions or appends.
- Is the shortest result unique? Yes, it is determined by the longest palindromic prefix.
- Can s be empty? Yes; return "".
02Brute force
For k from n down to 0, test whether s[:k] is a palindrome; the first one found gives the answer.
Cost: O(n²): on "aaaa...ab" each test is nearly n long and there are n tests, about 10^9 steps at n = 5·10^4.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.