# LeetCode 214: Shortest Palindrome

## Problem Restatement

We are given a string `s`.

We may add characters only in front of `s`.

We need to return the shortest palindrome that can be created this way.

The official statement says we can convert `s` to a palindrome by adding characters in front of it, and we must return the shortest palindrome possible.

## Input and Output

| Item | Meaning |
|---|---|
| Input | String `s` |
| Output | Shortest palindrome formed by adding characters in front |
| Allowed operation | Add characters only before `s` |
| Constraint | `0 <= s.length <= 5 * 10^4` |
| Characters | Lowercase English letters |

Example function shape:

```python
def shortestPalindrome(s: str) -> str:
    ...
```

## Examples

Example 1:

```python
s = "aacecaaa"
```

The shortest palindrome is:

```python
"aaacecaaa"
```

We add one `"a"` in front.

Example 2:

```python
s = "abcd"
```

The shortest palindrome is:

```python
"dcbabcd"
```

We add `"dcb"` in front.

These are the standard examples for the problem.

## First Thought

Since we can only add characters to the front, the original string `s` must remain as the suffix of the final answer.

So the final answer looks like:

```text
some_added_characters + s
```

To make the whole string a palindrome, the part of `s` that already works best should stay in place.

That part is the longest prefix of `s` that is already a palindrome.

## Key Insight

Find the longest palindromic prefix of `s`.

Suppose:

```python
s = "abcd"
```

The longest palindromic prefix is:

```python
"a"
```

The remaining suffix is:

```python
"bcd"
```

To make a palindrome, reverse that suffix and add it to the front:

```python
"dcb" + "abcd" = "dcbabcd"
```

For:

```python
s = "aacecaaa"
```

The longest palindromic prefix is:

```python
"aacecaa"
```

The remaining suffix is:

```python
"a"
```

Reverse the suffix and add it to the front:

```python
"a" + "aacecaaa" = "aaacecaaa"
```

So the problem becomes:

```text
How do we find the longest palindromic prefix efficiently?
```

## Brute Force Prefix Check

We could check every prefix from longest to shortest.

For each prefix:

1. Check if it is a palindrome.
2. If yes, use it.

```python
class Solution:
    def shortestPalindrome(self, s: str) -> str:
        for end in range(len(s), -1, -1):
            prefix = s[:end]

            if prefix == prefix[::-1]:
                suffix = s[end:]
                return suffix[::-1] + s

        return s
```

This is simple, but it may take quadratic time because each palindrome check copies and reverses a prefix.

For length up to `5 * 10^4`, we want a linear method.

## KMP Idea

KMP can find the longest prefix of one string that is also a suffix of another combined string.

We build:

```python
combined = s + "#" + reversed_s
```

The separator `"#"` prevents accidental matching across the boundary.

The last value of the KMP prefix table tells us the length of the longest prefix of `combined` that is also a suffix of `combined`.

Because of how we built the string, this value becomes the length of the longest palindromic prefix of `s`.

## Why This Works

Let:

```python
s = "aacecaaa"
reversed_s = "aaacecaa"
combined = "aacecaaa#aaacecaa"
```

The longest prefix of `combined` that is also a suffix is:

```python
"aacecaa"
```

This means:

- it appears at the start of `s`
- it appears at the end of `reversed_s`

A prefix of `s` appearing at the end of `reversed_s` means that prefix reads the same forward and backward.

So it is a palindromic prefix.

## Prefix Table

The KMP prefix table is usually called `lps`.

`lps[i]` means:

```text
the length of the longest proper prefix of combined[0:i+1]
that is also a suffix of combined[0:i+1]
```

Example idea:

```text
combined = "abab"
```

For the full string `"abab"`:

- prefix `"ab"`
- suffix `"ab"`

So the last `lps` value is `2`.

For this problem, we only need the final `lps` value.

## Algorithm

1. Reverse `s`.
2. Build `combined = s + "#" + reverse(s)`.
3. Compute the KMP `lps` array for `combined`.
4. Let `prefix_len = lps[-1]`.
5. The suffix after the palindromic prefix is `s[prefix_len:]`.
6. Reverse that suffix and put it in front of `s`.

## Walkthrough

Use:

```python
s = "abcd"
```

Reverse:

```python
reversed_s = "dcba"
```

Combined string:

```python
"abcd#dcba"
```

The longest palindromic prefix has length `1`, which is:

```python
"a"
```

Suffix after that prefix:

```python
"bcd"
```

Reverse suffix:

```python
"dcb"
```

Answer:

```python
"dcb" + "abcd" = "dcbabcd"
```

## Correctness

The final answer must keep `s` unchanged as its suffix because we are only allowed to add characters before it.

To minimize the number of added characters, we need to maximize the part of `s` that already belongs to the front-side palindrome structure. This part must be a prefix of `s`, and it must itself be a palindrome.

So the optimal strategy is to find the longest palindromic prefix of `s`.

The KMP construction `s + "#" + reverse(s)` computes the longest prefix of `s` that also matches a suffix of `reverse(s)`. Such a match means the prefix reads the same forward and backward, so it is a palindromic prefix.

The separator prevents matches from crossing between `s` and `reverse(s)`.

After finding this longest palindromic prefix, every remaining character in the suffix must be mirrored before `s`. Adding the reverse of that suffix to the front is sufficient and uses the fewest possible characters.

Therefore the algorithm returns the shortest palindrome obtainable by adding characters in front.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Build reverse string and one KMP table |
| Space | `O(n)` | Store combined string and `lps` array |

## Implementation

```python
class Solution:
    def shortestPalindrome(self, s: str) -> str:
        reversed_s = s[::-1]
        combined = s + "#" + reversed_s

        lps = [0] * len(combined)

        for i in range(1, len(combined)):
            length = lps[i - 1]

            while length > 0 and combined[i] != combined[length]:
                length = lps[length - 1]

            if combined[i] == combined[length]:
                length += 1

            lps[i] = length

        prefix_len = lps[-1]
        suffix = s[prefix_len:]

        return suffix[::-1] + s
```

## Code Explanation

Reverse the string:

```python
reversed_s = s[::-1]
```

Build the KMP input:

```python
combined = s + "#" + reversed_s
```

Create the prefix table:

```python
lps = [0] * len(combined)
```

For each position, start from the previous matched length:

```python
length = lps[i - 1]
```

If the next character does not match, fall back to a shorter border:

```python
while length > 0 and combined[i] != combined[length]:
    length = lps[length - 1]
```

If it matches, extend the current border:

```python
if combined[i] == combined[length]:
    length += 1
```

Store it:

```python
lps[i] = length
```

The final value gives the longest palindromic prefix length:

```python
prefix_len = lps[-1]
```

Take the unmatched suffix:

```python
suffix = s[prefix_len:]
```

Reverse it and add it in front:

```python
return suffix[::-1] + s
```

## Simpler Two-Pointer Recursive Version

There is also a compact recursive solution.

```python
class Solution:
    def shortestPalindrome(self, s: str) -> str:
        i = 0

        for j in range(len(s) - 1, -1, -1):
            if s[i] == s[j]:
                i += 1

        if i == len(s):
            return s

        suffix = s[i:]

        return suffix[::-1] + self.shortestPalindrome(s[:i]) + suffix
```

This version is shorter, but the KMP version gives a clean linear-time guarantee.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.shortestPalindrome("aacecaaa") == "aaacecaaa"
    assert s.shortestPalindrome("abcd") == "dcbabcd"
    assert s.shortestPalindrome("") == ""
    assert s.shortestPalindrome("a") == "a"
    assert s.shortestPalindrome("aba") == "aba"
    assert s.shortestPalindrome("abb") == "bbabb"
    assert s.shortestPalindrome("aaab") == "baaab"

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `"aacecaaa"` | Standard example |
| `"abcd"` | Only first character is palindromic prefix |
| `""` | Empty string |
| `"a"` | Single character |
| `"aba"` | Already palindrome |
| `"abb"` | Prefix length one |
| `"aaab"` | Long repeated prefix |