<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 calculate_z(self, s):

        n = len(s)  # Length of the input string
        z = [0] * n  # Initialize Z-array with zeros
        l, r, k = 0, 0, 0  # Initialize left and right boundary of Z-box

        for i in range(1, n):

        # Case 1: i is outside the current Z-box
            if i > r:
                l, r = i, i
                while r < n and s[r] == s[r - l]:
                    r += 1
                z[i] = r - l
                r -= 1

                # Case 2: i is inside the current Z-box
            else:
                k = i - l

                # Case 2a: Value does not stretch outside the Z-box
                if z[k] < r - i + 1:
                    z[i] = z[k]

                    # Case 2b: Value stretches outside the Z-box
                else:

                # Case 2b: Value stretches outside the Z-box
                    l = i
                    while r < n and s[r] == s[r - l]:
                        r += 1
                    z[i] = r - l
                    r -= 1
        return z


    def shortestPalindrome(self, s: str) -> str:
        if len(s) == 0:
            return s
        if len(s) == 1:
            return s
        

        zz = self.calculate_z(s + s[::-1])
        for i in range(len(s), 2*len(s)):
            if zz[i] + i >= 2*len(s):
                j = i - len(s)
                return s[len(s) - j:][::-1] + s
        return s[::-1] + s 
        

20100