**Solution**

**Shortest Palindrome** https://leetcode.com/problems/shortest-palindrome/

- X = "abcd". If we reverse X and add it to front of X, we will for sure have a palindrome."dcbaabcd".
- However there may be redundant characters in this palindrome which doesnt make it the shortest. For example: "dcbabcd" is a valid palindrome with one less character. Try other examples: s="ananab". rev_s = "banana". New Palindrom: "bananaananab". Shorter one: "banananab"
- The general approach is then: X = PS. P is the longest prefix which is also a palindrome. S is remainder suffix. Thus the new palindrome is: New palindrom = SPS. Implementing above in a naive manner gives you an N^2 algorithm.
- Notice one more thing: X = "ananab" and R_X = "banana". Longest prefix in X which is a suffix in R_X is "anana". Remove that from R_X and we have "ban" + "ananab" as palindrome.
- KMP can be used to solve *Longest prefix in X which is a suffix in RX *
- Another interesting idea is to use
**startswith**API in Python. s.startswith(rev_s[i:]) and we vary i from 0 to N. This automatically gives us the longest prefix to work with.

https://discuss.leetcode.com/topic/14542/ac-in-288-ms-simple-brute-force

```
class Solution(object):
def shortestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
if s == "":
return s
rev_s = s[::-1]
for i in range(len(s)):
if s.startswith(rev_s[i:]):
return rev_s[:i]+s
```