> For the complete documentation index, see [llms.txt](https://maksimdan.gitbook.io/interview-practice-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/214-shortest-palindrome.md).

# 214 Shortest Palindrome

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

For example:

Given`"aacecaaa"`, return`"aaacecaaa"`.

Given`"abcd"`, return`"dcbabcd"`.

Brute Force idea: check for matching substrings

```
Ex1:

abcd
dcba
abc
cba
ab
ba
a
a

Ex2:
adcbabcd
aacecaaa
aaacecaa
aacecaa
aacecaa
```

```cpp
string shortestPalindrome(string s) {
    string r = s;
    reverse(r.begin(), r.end());

    const size_t size = s.length();
    int i = 0;
    for (i; i < size; i++) {
        if (s.substr(0, size - i) == r.substr(i))
            break;
    }

    return r.substr(0, i) + s;
}


int main()
{
    cout << shortestPalindrome("abcd") << endl;
    cout << shortestPalindrome("aacecaaa") << endl;
}
```