# 214. Shortest Palindrome

## Problem Statement

<br>

You are given a string `s`. You can convert `s` to a&#x20;

palindrome by adding characters in front of it.

Return *the shortest palindrome you can find by performing this transformation*.

&#x20;

**Example 1:**

<pre><code><strong>Input: s = "aacecaaa"
</strong><strong>Output: "aaacecaaa"
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: s = "abcd"
</strong><strong>Output: "dcbabcd"
</strong></code></pre>

&#x20;

**Constraints:**

* `0 <= s.length <= 5 * 104`
* `s` consists of lowercase English letters only.

## Intuition

```
Approach : KMP Prefix suffix

s = anab
Output = b)anab

reverse String  = bana
Attach at end

anab#bana
Run longest Prefix Suffix, by that we can come to know about longest match aba
and we can eliminate that
and just put that extra b at start again to get

banab
```

### Links

<https://leetcode.com/problems/shortest-palindrome/description/>

### Video Links

<https://www.youtube.com/watch?v=c4akpqTwE5g&ab_channel=IDeserve>

### Approach 1:

```
KMP
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    string shortestPalindrome(string s) {
        if(s.size() == 0)   return "";
        string rev = s;
        reverse(rev.begin(), rev.end());
        // Make a distinction, otherwise it'll match entire
        string temp = s + "#" + rev;

        // Apply LPS KMP
        vector<int> lps(temp.size(), 0);
        int prev=0, i=1;

        while(i<temp.size()){
            if(temp[i] == temp[prev]){
                lps[i] = prev + 1;
                prev++; i++;
            }
            else if(prev == 0){
                lps[i] = 0;
                i++;
            }
            else
                prev = lps[prev-1];
        }

        int last_val = lps.back();

        return rev.substr(0, rev.size() - last_val) + s;
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###