<p>Given a string <code>s</code>, return <em>the longest</em> <span data-keyword="palindromic-string"><em>palindromic</em></span> <span data-keyword="substring-nonempty"><em>substring</em></span> in <code>s</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;babad&quot;
<strong>Output:</strong> &quot;bab&quot;
<strong>Explanation:</strong> &quot;aba&quot; is also a valid answer.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;cbbd&quot;
<strong>Output:</strong> &quot;bb&quot;
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 1000</code></li>
	<li><code>s</code> consist of only digits and English letters.</li>
</ul>

class Solution {
public:
    string longestPalindrome(string s) {

        //init the string with #
        string str = "#";
        for(int i = 0; i < s.length(); i++){
            str = str + s[i] + "#";
        }

        //init some variable
        int* LPS = new int[str.length()];
        int max_Z = 0, C = 0, R = 0;    //maxZ(i) and the center and right of the bigger array
        //processing
        for(int i = 0; i < str.length(); i++){

            //init LPS[i] of loop
            //case 1:(i>=R) need calc LPS from beginning
            if(i >= R)
                LPS[i] = 0;
            //case 2 and 3:(i<R) calc LPS from min(R-i or LPS[i_mirror](cuz LPS[i_mirror] is calculated))
            else{
                int i_mirror = C - (i - C);
                LPS[i] = min(LPS[i_mirror], R - i);
            }

            //init the l and r when the first calc
            int l = i - LPS[i] - 1;
            int r = i + LPS[i] + 1;
            LPS[i] = Z(str, LPS[i], l, r);

            //update if LPS[i] > current max_Z
            if(LPS[i] > max_Z){
                C = i;
                R = C + LPS[i];
                max_Z = LPS[i];
            }
        }
        delete [] LPS;

        //get the final answer (longest palindromic substring)
        string ans;
        for(int i = C - max_Z; i < C + max_Z; i++){
            if(str[i] == '#')
                continue;
            ans = ans + str [i];
        }
        return ans;
    }

    //calc Z(i), Z(i) is radius of the substring 
    int Z(string str, int init_Z, int left, int right){

        //if l and r didn't out of range and s[l]=s[r], Z(i)+1
        while(left >= 0 && right <= str.length() && str[left] == str[right]){
            init_Z++;
            left--;
            right++;
        }
        return init_Z;
    }
};
446353