<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 IsPalindromicSubstring(const string &s)
    {
        //cout << s << endl;
        int dwLength = s.length();
        for (int i = 0; i < dwLength / 2; i++)
        {
            if (s[i] != s[dwLength - 1 - i])
            {
                return false;
            }
        }
        return true;
    }

    string longestPalindrome(string s) 
    {
        //cout << "string:" << s << endl;
        int dwLeft = 0;
        int dwRight = 0;
        std::unordered_map <char, std::set<int>> mapChar; //record the index of char already visited by i
        int dwLength = s.length();

        for (int i = 0; i < dwLength; i++)
        {
            if(mapChar.count(s[i]) > 0)
            {
                for (auto const &it : mapChar.find(s[i])->second)
                {
                //substr param1:start_idx param2:length
                if (IsPalindromicSubstring(s.substr(it, i - it + 1)))
                    {
                        //compare max length
                        if (i - it > dwRight - dwLeft)
                        {
                            dwLeft = it;
                            dwRight = i;
                        }
                    }
                }
                //maybe palindrome
                //refresh pos
                mapChar.find(s[i])->second.insert(i);
            }
            else
            {
                std::set<int> setIndex;
                setIndex.insert(i);
                mapChar[s[i]] = setIndex;
            }
        }

        //for (auto const& it : mapChar)
        //{
        //    for (auto const &it1: it.second)
        //    cout << it.first << " " << it1 << endl;
        //}

        return s.substr(dwLeft, dwRight - dwLeft + 1);
    }
};
488676