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

// longest_palindromic_substr
class Solution {
public:
    int checkPara(string s, int left, int right, bool &loop) {
        if (loop) {
            if (((left-1)<0 && s[left]!=s[right+1]) || ((right+1)>=s.size() && s[left-1]!=s[right]))
                loop = false;
            if ((left-1)>=0 && (right+1)<s.size())
                if (s[left]!=s[left-1] && s[right]!=s[right+1])
                    loop = false;
        }
        if ((left-1)>=0 && (right+1)<s.size())
            if (s[left-1] == s[right+1])
                return 0;
        if ((left-1) >= 0)
            if (loop==true && s[left-1]==s[right])
                return 1;
        if ((right+1) < s.size())
            if (loop==true && s[left]==s[right+1])
                return 2;
        return 3;
    }

    string longestPalindrome(string s) {
        int left, right;
        int smin, smax;
        int max = 0;
        for (int i=0; i<s.size(); i++) {
            left = i;
            right = i;
            bool loop = true;
            while (checkPara(s, left, right, loop) != 3) {
                if (checkPara(s, left, right, loop) == 0) {
                    left-=1;
                    right+=1;
                }
                else if (checkPara(s, left, right, loop) == 1)
                    left-=1;
                else if (checkPara(s, left, right, loop) == 2)
                    right+=1;
            }
            if (max < right-left+1) {
                max = right - left + 1;
                smin = left;
                smax = right;
            }
            if (smax - smin + 1 == s.size())
                break;
        }
        string ret = "";
        for (int i=smin; i<=smax; i++)
            ret += s[i];
        return ret;
    }
};

422168