C++ linear solution O(n) time


  • 0
    S

    Manacher's algorithm
    https://en.wikipedia.org/wiki/Longest_palindromic_substring

       class Solution {
        public:
            string longestPalindrome(string s) {
                if (s.size() < 2) return s;
    
                string st(2 * s.size() + 1, '*'); // create new string, we simulate odd case palindrom in all cases
                for (int i = 0; i < s.size(); ++i) {
                    st[2 * i + 1] = s[i];
                }
    
                vector<int> pal(st.size());
                int pal1 = 0, left = 0, right = 0;
                for (int i = 0; i < st.size(); ++i) {
                    if (i < right) {
                        int mirror = 2 * pal1 - i;
                        if (pal[mirror] < mirror - left) {
                            pal[i] = pal[mirror];
                            continue;
                        }
                        if (pal[mirror] > mirror - left) {
                            pal[i] = mirror - left;
                            continue;
                        }                
                        if (pal[mirror] == mirror - left) {
                            pal[i] = mirror - left;
                        }                
                    } else {
                        right = i;
                    }
                    while (right + 1 < st.size() && right - 2 * pal[i] - 1 >= 0 && 
                            st[right + 1] == st[right - 2 * pal[i] - 1]) {
                                right++;
                                pal[i]++;
                    }
                    left = right - 2 * pal[i];
                    pal1 = i;
                }
                auto it = max_element(pal.begin(), pal.end());
    
                string answ_z, answ;
                answ_z = st.substr(it - pal.begin() - *it, 2 * *it + 1);
                for (int i = 0; i < answ_z.size(); ++i) { // convert answer to correct form
                    if (answ_z[i] != '*') {
                        answ += answ_z[i];
                    }
                }
                return answ;
            }
        };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.