<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 longestPalindrome(string s) {
        int n = s.size();
        unordered_map < char, vector<int>> hash;

        for (int i = 0; i < s.size(); i++) {
            hash[s[i]].push_back(i);
        }

        string maxPalindrome = "";
        int maxSize = 0;
        bool skip = false; // If can skip rest of backwards search

        for (int i = 0; i < n; i++) { // Loops from left to right through the string
            if (maxSize >= (n - i)) // if the largest palindrome so far is larger than the rest of the checkable strings, return
                return maxPalindrome;

            vector<int> indexes = hash[s[i]];
            int indexNums = indexes.size();

            if (indexNums > 1) { // Check if there are more 
                for (int t = indexNums-1; t > 0; t--) { // Loops through the indexes where the starting char exists
                    int index = indexes[t];
                    if ((index - i) < maxSize) // If indexes are too close together to be bigger than largest palindrome
                        break;
                    string palindrome(index - i + 1, '.'); // Placeholder string
                    int size = 2;
                    palindrome[0] = s[i];
                    palindrome[index - i] = s[index];
                    skip = true;
                    for (int x = 1; x <= (index-i)/2.0; x++) {
                        if (s[i+x] == s[index-x]) {
                            if (i + x == index - x) {   
                                size += 1;
                            } else { // Else add two, for adding one on left and one on right
                                size += 2;
                            }
                            palindrome[x] = s[i + x];
                            palindrome[index - i - x] = s[index - x];
                        } else {
                            skip = false;
                            size = 0;
                            break;
                        }
                    }

                    if (size > maxSize) {
                        maxSize = size;
                        maxPalindrome = palindrome;
                    }
                    
                    if (skip) break;

                }
            } 
            hash[s[i]].erase(hash[s[i]].begin()); // Remove the first value in the vector
        }

        if (maxSize == 0 && maxPalindrome == "")
            maxPalindrome = s[0];

        return maxPalindrome;
    }
};
349613