Build the Shortest Palindrome by Prepending Only
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
Add characters only in front of s to make it a palindrome. Return the shortest resulting palindrome. Preserve all existing characters and their order; appending at the end or inserting inside s is not allowed.
```cpp
string shortestPalindrome(string s);
```
### Examples
```text
Input: s = "abb"
Output: "bbabb"
```
```text
Input: s = "race"
Output: "ecarace"
```
### Constraints
- Length is between 0 and 50000.
- Only lowercase English letters occur.
Overview: Construct the shortest prepend-only palindrome from the longest palindromic prefix found by a delimiter-safe prefix function.