<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 getPalindrom(const string& s, int pos0, int pos1) {
        if (pos0 < 0) return "";
        if (pos1 >= s.size()) return "";
        if (pos0 > pos1) return "";

        string ps(s.begin() + pos0, s.begin() + pos1 + 1);

        //cout << "ps " << ps << endl;

        if (pos0 == 0 || pos1 == s.size() - 1)
            return ps;

        int i = 1;
        char s0 = s[pos0 - i];
        char s1 = s[pos1 + i];

        while (s0 == s1) {
            ps = s0 + ps + s1;
            i++;
            if (pos0 - i < 0) break;
            if (pos1 + i >= s.size()) break;
            s0 = s[pos0 - i];
            s1 = s[pos1 + i];
        }

        return ps;
    }

    string longestPalindrome0(string s) {
        if (s.empty()) return "";
        if (s.size() == 1) return s;

        string max_pal(1, s[0]);
        if (s[0] == s[1]) {
            max_pal = string("") + s[0] + s[1];
        }
        int i0 = 0;
        int i1 = 2;
        while (i1 < s.size()) {
            int step = 1;
            string ps = "";
            if (s[i0 + 1] == s[i1]) {
                ps = getPalindrom(s, i0 + 1, i1);
                if (ps.size() > max_pal.size()) {
                    max_pal = ps;
                }
            }

            if (s[i0] == s[i1]) {
                ps = getPalindrom(s, i0, i1);
                if (ps.size() > max_pal.size()) {
                    max_pal = ps;
                }
            }

            i0++;
            i1++;
        }

        //cout << getPalindrom("1234567650000000", 6, 6) << endl;
        //cout << getPalindrom("1234567765000 0", 6, 6) << endl;
        //       |    |
        // "123456765000000" step 5
        //       |
        // "1234567765 0000000"

        return max_pal;
    }

    
    string longestPalindrome(string s) {
        //s = "700000002011151113144";
        if (s.empty()) return "";
        if (s.size() == 1) return s;

        deque<pair<int, int>> repetitions;

        int i0 = 0;
        for (int i = 1; i < s.size(); i++) {
            if (s[i] == s[i - 1]) {
                if (i == s.size() - 1) {
                    repetitions.push_back(make_pair(i0, i));
                    //cout << "rep " << i0 << " " << i << endl;
                }
                continue;
            }
            else if (s[i] != s[i - 1] && i - 1 > i0) {
                repetitions.push_back(make_pair(i0, i - 1));
                //cout << "rep " << i0 << " " << i - 1 << endl;
                i0 = i;
            }
            else 
                i0 = i;
        }

        vector<int> triplet_centers;
        repetitions.push_front(make_pair(0, 0));
        repetitions.push_back(make_pair(s.size() - 1, s.size() - 1));

        for (int i = 1; i < repetitions.size(); i++) {
            int i0 = repetitions[i - 1].second + 1;
            int i1 = repetitions[i].first - 1;

            for (int j = i0; j <= i1; j++) {
                if (s[j - 1] == s[j + 1]) {
                    triplet_centers.push_back(j);
                    //cout << "triplet center " << j << endl;
                }
            }
        }

        string best_pal = "";

        for (int i = 1; i < repetitions.size() - 1; i++) {
            int i0 = repetitions[i].first;
            int i1 = repetitions[i].second;
            string ps = getPalindrom(s, i0, i1);
            if (ps.size() > best_pal.size()) {
                best_pal = ps;
            }
        }

        for (int i = 0; i < triplet_centers.size(); i++) {
            int i0 = triplet_centers[i] - 1;
            int i1 = triplet_centers[i] + 1;
            string ps = getPalindrom(s, i0, i1);
            if (ps.size() > best_pal.size()) {
                best_pal = ps;
            }
        }

        if (best_pal == "" && s.size() > 0) return string(1, s[0]);

        return best_pal;
    }
};
404029