Preparing this workspace.
Shortest Palindrome
Difficulty: Hard
Category: DSA
Topics: String, Rolling Hash, String Matching, Hash Function
Asked at: Microsoft
You are given a string `s`. You can convert `s` to a palindrome by adding characters in front of it.
Return _the shortest palindrome you can find by performing this transformation_.
**Example 1:**
**Input:** s = "aacecaaa"
**Output:** "aaacecaaa"
```
**Example 2:**
**Input:** s = "abcd"
**Output:** "dcbabcd"
```
**Constraints:**
- `0 <= s.length <= 5 * 104`
- `s` consists of lowercase English letters only.
Opening the problem
Progress is saved as you study.