<p>You are given a string <code>s</code>. You can convert <code>s</code> to a <span data-keyword="palindrome-string">palindrome</span> by adding characters in front of it.</p>

<p>Return <em>the shortest palindrome you can find by performing this transformation</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> s = "aacecaaa"
<strong>Output:</strong> "aaacecaaa"
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> s = "abcd"
<strong>Output:</strong> "dcbabcd"
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>0 &lt;= s.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>s</code> consists of lowercase English letters only.</li>
</ul>

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        return self._sol1(s)

    # Perf: 42.0% 102 ms, 5.9% 20.7 mb. There's a small memory curve around where I am, most is around 16.5 - 17.1 mb.
    #   So one improvement is that I missed that we're only allowed to add characters to the left. That should allow some
    #   simplifications. Hmm actually no will still need the full Manacher's, as finding positions that can't serve as pivots doesn't
    #   mean we won't find a later one. But, we don't need to examine the last half of the string, because ultimately we need a location
    #   where the index is equal to the radius at that index, and we can't have a radius greater than half the size.
    # Alright made some optimizations since only adding to the left, 67.6% 64 ms, 24.3% 18.9 mb.
    def _sol1(self, s: str) -> str:
        if s == s[::-1]:
            return s
        new_s = "|".join(list(s))
        # Manacher's algorithm for getting longest palindrome from each position
        max_pivot_i = len(new_s) // 2 # len(new_s) is always odd so center is // 2 + 1, but subtract 1 because zero-indexed
        pal_rads = [0] * (max_pivot_i + 1)
        center = 0
        trial_radius = 1
        while center <= max_pivot_i:
            while (center - trial_radius >= 0 and center + trial_radius < len(new_s) and
                   new_s[center - trial_radius] == new_s[center + trial_radius]):
                trial_radius += 1
            old_cen = center
            old_rad = trial_radius - 1
            pal_rads[old_cen] = old_rad
            center += 1
            trial_radius = 1
            while center <= max_pivot_i and center <= old_cen + old_rad:
                comparison_rad = old_cen + old_rad - center
                mirror_rad = pal_rads[old_cen - (center - old_cen)]
                if mirror_rad < comparison_rad:
                    # Less than the bounds of the larger palindrome, so this is ours too
                    pal_rads[center] = mirror_rad
                elif mirror_rad > comparison_rad:
                    pal_rads[center] = comparison_rad
                else:
                    trial_radius = comparison_rad + 1
                    break
                center += 1
        # We now have a record of the longest palindrome stemming from each position in new_s, which is s interleaved with "|"
        # Iterate through and find the most suitable position, which is the highest
        for i in range(max_pivot_i, -1, -1):
            if pal_rads[i] == i:
                best_i = i
                break
        # Now construct the smallest palindrome string
        radius = pal_rads[best_i]
        # We're adding to the left
        padded_palindrome = new_s[:best_i + radius:-1] + new_s
        return "".join(char for char in padded_palindrome if char != "|")
        
    # Perf: hah! better mem but 5.1% time, 5538 ms! 92 times slower or so!
    def _low_mem_found(self, s: str) -> str:
        def check(t):
            l = len(t)
            if l==1: return True 
            if l%2==1: L, R = l//2, l//2 # odd: ...bab...
            else: L, R = l//2-1, l//2 # even: ...aa...
            while L>=0:
                if t[L]!=t[R]: return False
                L, R = L-1, R+1
            return True
        t, n = s, len(s)-1
        while not check(t) and n>=0:
            t = s[n:] 
            t = t[::-1] + s 
            #print(n, t)
            n -= 1
        return t
19000