<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:
    bool isPalindrome(string s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s[left] != s[right]) return false;
            left++;
            right--;
        }
        return true;
    }

    bool palindromeExist(string s, int len) {
        int left = 0;
        while (left + len <= s.length()) {
            if (isPalindrome(s.substr(left, len))) {
                return true;
            }
            left++;
        }
        return false;
    }

    string findPalindrome(string s, int len) {
        int left = 0;
        while (left + len <= s.length()) {
            if (isPalindrome(s.substr(left, len))) {
                return s.substr(left, len);
            }
            left++;
        }
        return "";
    }

    int findEvenPalindrome(string s) {
        if (!palindromeExist(s, 2)) {
            return 0;
        }
        int left = 2, right = s.length(), mid, ans;
        while (left <= right) {
            mid = (left + right) / 2;
            if (mid % 2 != 0) mid--;
            if (palindromeExist(s, mid)) {
                ans = mid;
                left = mid + 2;
            } else {
                right = mid - 2;
            }
        }
        return ans;
    }

    int findOddPalindrome(string s) {
        if (!palindromeExist(s, 3)) {
            return 1;
        }
        int left = 3, right = s.length(), mid, ans;
        while (left <= right) {
            mid = (left + right) / 2;
            if (mid % 2 == 0) mid--;
            if (palindromeExist(s, mid)) {
                ans = mid;
                left = mid + 2;
            } else {
                right = mid - 2;
            }
        }
        return ans;
    }

    string longestPalindrome(string s) {
        if (s.length() == 1) return s;
        if (s.length() == 2) {
            if (isPalindrome(s)) {
                return s;
            }
            return s.substr(0, 1);
        }
        
        return findPalindrome(s, max(findEvenPalindrome(s), findOddPalindrome(s)));
    }
};
101716