<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>

bool palindromic_check(string s)
{
    bool flag = true;
    
    for (int i = 0; i < s.size() / 2; i++)
    {
        if (s[i] != s[s.size() - 1 - i])
        {
            flag = false;
            break;
        }
    }
    
    return flag;
}

string check_for_odd(string s)
{
    int n = s.size();
    
    vector<int> arr(n, 0);
    
    int max_length = 0;
    
    int i_max = 0;
    
    int l = 0, r = -1;
    
    for (int i = 0; i < n; i++)
    {
        int length = 0;
        
        if (i > r)
        {
            
            while ((i + length < n) && (i - length >= 0) && palindromic_check(s.substr(i - length, 2 * length + 1)))
            {
                length++;
            }
            
            length--;
            
            l = i - length;
            r = i + length;
        }
        else // if (i <= r)
        {
            length = arr[l + r - i];
            
            if (i + length < n && i - length >= 0)
            {
                
                while ((i + length < n) && (i - length >= 0) && palindromic_check(s.substr(i - length, 2 * length + 1)))
                {
                    length++;
                }
                
                length--;
                
                if (r < i + length)
                {
                    l = i - length;
                    r = i + length;
                }
            }
        }
        
        arr[i] = length;
        
        if (length > max_length)
        {
            max_length = length;
            i_max = i;
        }
    }
    
    string answer = s.substr(i_max - max_length, 2 * max_length + 1);
    
    return answer;
}

string check_for_even(string s)
{
    {
        int n = s.size();
        
        vector<int> arr(n, 0);
        
        int max_length = 0;
        
        int i_max = 0;
        
        int l = 0, r = -1;
        
        for (int i = 0; i < n; i++)
        {
            int length = 0;
            
            if (i > r)
            {
                while ((i + length < n) && (i - length + 1 >= 0) && palindromic_check(s.substr(i - length + 1, 2 * length)))
                {
                    length++;
                }
                
                length--;
                
                l = i - length + 1;
                r = i + length;
            }
            else // if (i <= r)
            {
                length = arr[l + r - i];
                
                if (i + length < n && i - length + 1 >= 0)
                {
                    
                    while ((i + length < n) && (i - length + 1 >= 0) && palindromic_check(s.substr(i - length + 1, 2 * length)))
                    {
                        length++;
                    }
                    
                    length--;
                    
                    if (r < i + length)
                    {
                        l = i - length + 1;
                        r = i + length;
                    }
                }
            }
            
            arr[i] = length;
            
            if (length > max_length)
            {
                max_length = length;
                i_max = i;
            }
        }
        
        string answer = s.substr(i_max - max_length + 1, 2 * max_length);
        
        return answer;
    }
}

class Solution
{
public:
    string longestPalindrome(string s)
    {
        string ans1 = check_for_odd(s);
        string ans2 = check_for_even(s);
        
        string answer = ans1.size() > ans2.size() ? ans1 : ans2;
        
        return answer;
    }
};

35208