# Question

Formatted question description: https://leetcode.ca/all/214.html

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.

# Algorithm

• In the worst-case scenario, where there are no identical characters in the string s, the minimum number of characters required to be added is s.size() - 1.
• In the first example, the string contains a palindrome. To form a complete palindrome, only one character needs to be added to the front.

To solve this, first reverse the string s to obtain t. Then, compare the original string s with the reversed string t, starting from the first character and proceeding one character at a time:

• If they are equal, it indicates that s is already a palindrome. No additional characters need to be added, and the function can return immediately.
• If they are not equal, remove the last character from s, remove the first character from t, and continue comparing. This process repeats until the strings are equal or the loop concludes.

This method ensures that the two strings are concatenated in the correct manner to form a palindrome.

### Examples:

Reversed:  a b c d a
s:                   a d c b a


Try to move both towards the center to find a possible overlap. By removing one character, we save an “a”.

Reversed:  a b c d a
s:                 a d c b a


Move further, “da” and “ad” overlap, and the remaining part, “abc” vs “cba”, forms a palindrome.

Reversed:  a b c d a
s:               a d c b a


Therefore, “da” and “ad” go to the next recursion.

Reversed:  d a
s:             a d


Moving one more character aligns the strings perfectly, yielding the final result.

Reversed:  d a
s:           a d


Another Example: “aacecaaa”

• The iteration stops at the last ‘a’, i=7.
• "a"+dfs("aacecaa")+"a"

This approach strategically reduces the problem size by identifying overlapping parts between the original and reversed strings, effectively minimizing the number of characters needed to transform the input into a palindrome.

# Code

• 
public class Shortest_Palindrome {

public class Solution {
public String shortestPalindrome(String s) {

if (s == null || s.length() == 0) {
return "";
}

int i = 0, n = s.length();
for (int j = n - 1; j >= 0; --j) { // @note: j will cross i, eg. making i=2 for "adcba"
if (s.charAt(i) == s.charAt(j)) {
++i;
}
}
// now [0, i) is a possible palindrome, but need extra check
if (i == n) {
return s;
}

String remaining = s.substring(i); // need to add reverse part of it
String rem_rev = new StringBuilder(remaining).reverse().toString();
return rem_rev + shortestPalindrome(s.substring(0, i)) + remaining;

}
}
}

############

class Solution {
public String shortestPalindrome(String s) {
int base = 131;
int mul = 1;
int mod = (int) 1e9 + 7;
int prefix = 0, suffix = 0;
int idx = 0;
int n = s.length();
for (int i = 0; i < n; ++i) {
int t = s.charAt(i) - 'a' + 1;
prefix = (int) (((long) prefix * base + t) % mod);
suffix = (int) ((suffix + (long) t * mul) % mod);
mul = (int) (((long) mul * base) % mod);
if (prefix == suffix) {
idx = i + 1;
}
}
if (idx == n) {
return s;
}
return new StringBuilder(s.substring(idx)).reverse().toString() + s;
}
}

• // OJ: https://leetcode.com/problems/shortest-palindrome/
// Time: O(N)
// Space: O(1) ignoring the space taken by the answer
class Solution {
public:
string shortestPalindrome(string s) {
unsigned d = 16777619, h = 0, rh = 0, p = 1, maxLen = 0;
for (int i = 0; i < s.size(); ++i) {
h = h * d + s[i] - 'a';
rh += (s[i] - 'a') * p;
p *= d;
if (h == rh) maxLen = i + 1;
}
return string(rbegin(s), rbegin(s) + s.size() - maxLen) + s;
}
};

• '''
reversed(): returns a reverse iterator

>>> s = "aabbcc"
>>> reversed(s)
<reversed object at 0x108384a60>
>>> ''.join(reversed(s))
'ccbbaa'

>>> s = "aabbcc"
>>> s[::-1]
'ccbbaa'
'''
class Solution:
def shortestPalindrome(self, s: str) -> str:
if not s:
return ""

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

if i == n:
return s

remaining = s[i:]
rem_rev = remaining[::-1]
return rem_rev + self.shortestPalindrome(s[:i]) + remaining

############

class Solution:
def shortestPalindrome(self, s: str) -> str:
base = 131
mod = 10**9 + 7
n = len(s)
prefix = suffix = 0
mul = 1
idx = 0
for i, c in enumerate(s):
prefix = (prefix * base + (ord(c) - ord('a') + 1)) % mod
suffix = (suffix + (ord(c) - ord('a') + 1) * mul) % mod
mul = (mul * base) % mod
if prefix == suffix:
idx = i + 1
return s if idx == n else s[idx:][::-1] + s

############

class Solution(object):
# brutal force TLE
def _shortestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""

def isPal(cand):
start, end = 0, len(cand) - 1
while start < end:
if cand[start] != cand[end]:
return False
start += 1
end -= 1
return True

n = len(s)
ans = s[::-1] + s
ansLen = 2 * len(s)
for i in reversed(range(0, len(s) + 1)):
newPal = s[i:][::-1] + s
if isPal(newPal) and n + len(s) - i < ansLen:
ansLen = n + len(s) - i
ans = newPal
return ans

def shortestPalindrome(self, s):
r = s[::-1]
for i in range(len(s) + 1):
if s.startswith(r[i:]):
return r[:i] + s


• func shortestPalindrome(s string) string {
n := len(s)
base, mod := 131, int(1e9)+7
prefix, suffix, mul := 0, 0, 1
idx := 0
for i, c := range s {
t := int(c-'a') + 1
prefix = (prefix*base + t) % mod
suffix = (suffix + t*mul) % mod
mul = (mul * base) % mod
if prefix == suffix {
idx = i + 1
}
}
if idx == n {
return s
}
x := []byte(s[idx:])
for i, j := 0, len(x)-1; i < j; i, j = i+1, j-1 {
x[i], x[j] = x[j], x[i]
}
return string(x) + s
}

• // https://leetcode.com/problems/shortest-palindrome/

using System.Text;

public partial class Solution
{
public string ShortestPalindrome(string s)
{
for (var i = s.Length - 1; i >= 0; --i)
{
var k = i;
var j = 0;
while (j < k)
{
if (s[j] == s[k])
{
++j;
--k;
}
else
{
break;
}
}
if (j >= k)
{
var sb = new StringBuilder(s.Length * 2 - i - 1);
for (var l = s.Length - 1; l >= i + 1; --l)
{
sb.Append(s[l]);
}
sb.Append(s);
return sb.ToString();
}
}

return string.Empty;
}
}

• impl Solution {
pub fn shortest_palindrome(s: String) -> String {
let base = 131;
let (mut idx, mut prefix, mut suffix, mut mul) = (0, 0, 0, 1);
for (i, c) in s.chars().enumerate() {
let t = c as u64 - '0' as u64 + 1;
prefix = prefix * base + t;
suffix = suffix + t * mul;
mul *= base;
if prefix == suffix {
idx = i + 1;
}
}
if idx == s.len() {
s
} else {
let x: String = (&s[idx..]).chars().rev().collect();
String::from(x + &s)
}
}
}