My 4 ms C++ solution


  • 0
    S

    The basic idea here is that I run through the sequence of characters and try to find the longest possible palindrome that starts at the beginning of the string. Once identified I take the remainder of the string reverse it and prefix it onto the original string.

    The identification of the longest possible palindrome (starting at the first character of the string) is identified by running through the sequence and summing up the difference and cubed difference between current character and the previous character. Upon encountering a complete palindrome both the sum of the difference and cubed difference should be zero. Such positions are stored in a stack and are explored in reverse to identify the largest palindromic sub-sequence.

    class Solution
    {
    public:
        string shortestPalindrome(string s)
        {
            stack <int> zero_pos;
            size_t length = s.length();
            if(length <= 1)
            {
                return s;
            }
            int cur_sum  = 0, cur_sum_cubed = 0;
            int max_palindrome_pos = 0;
            int pos;
            int diff;
    
            for(int i = 1; i < length; i++)
            {
                diff = s[i] - s[i-1];
                cur_sum += diff;
                cur_sum_cubed += diff*diff*diff;
                if (cur_sum == 0 && cur_sum_cubed == 0)
                {
                    zero_pos.push(i);
                }
            }
    
            while(!zero_pos.empty())
            {
                pos = zero_pos.top();
                zero_pos.pop();
                if(this->isPalindrome(s, 0, pos))
                {
                    max_palindrome_pos = pos;
                    break;
                }
            }
    
            string prefix = s.substr(max_palindrome_pos + 1);
            reverse(prefix.begin(), prefix.end());
    
            prefix += s;
    
            return prefix;
        }
    
        bool isPalindrome(string s, int start, int stop)
        {
            int length = stop - start + 1;
            int i = 0;
    
            while(s[start + i] == s[start + length -1 - i] && i < length/2)
            {
                i++;
            }
    
            if (i < length/2)
                return false;
            return true;
        }
    };

  • 0
    K

    Good idea, but it's not O(n)


  • 0
    S

    Asymptotically speaking? What's the complexity then?


  • 0
    J

    The idea is brilliant! I do believe this is an expected O(n) algorithm, and it converges in probability to O(n) as you include diff^5, diff^7 so on so forth. But I don't know how to prove it...


Log in to reply
 

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