C++ solution (6ms,O(N^2),O(1) space) you could actually come up with in an interview


  • 0
    F
    /*
    * Palindromes can be odd in length, eg "abcbcba" or even in length eg; "adsffsda"
    * We'll define the "left edge" of a palindrome as its starting index and its "right edge" as its ending index.
    * We define the set of minimal odd palindromes (length 3). A minimal odd palindrome simply needs s[i] = s[i+2] given a character array "s" and indices 0<=i<=N where N is len(s). There will be at most N/3 such palindromes.
    * We define the set of minimal even palindromes (length = 2) as a pair of consecutive equal characters. There will be at most N/2 such palindromes.
    * Before doing anything else, we handle the trivial cases: 
    * To find the above set, we start at the middle of the string and iterate to one side. In each iteration of this loop, we check:
        do we have a minimal even palindrome? do we have one on the mirror side?
        do we have a minimal odd palindrome? do we have one on the mirror side?
        If the answer to any of these questions is yes, we try to expand it outwards O(N). We compare its final size to the "best". If it's better, this is the new best.  
        We move from the middle outwards because minimal palindromes found closer to the center of the
        string are potentially larger (they can literally have a bigger size) than minimal palindromes
        found near the edges. Since we care about the largest palindrome, it makes sense to operate in
        this order.
     *  Once we reach a point in our loop where the largest palindrome we've found is larger than the biggest potential palindrome we could find in this part of the string, we're done and break out of the loop. Otherwise we continue until we reach the edge of the string. We return the best palindrome
     * Runtime complexity is O(N^2) since we have an O(N) loop searching for minimal palindromes and checking each one is O(N). Space complexity is O(1) since we only store the best palindrome and overwrite it as necessary.
    */
    struct Palindrome
    {
        int start;
        int size;
    public:
        Palindrome(int st=0, int sz=0) : start(st), size(sz) {};
        int potential(int n) const //returns potential size given the size of the original string
        {
            int left_potential = start; //maximum size this palindrome can grow left
            int right_potential = std::max(0,n - (start + size)); //maximum size this palindrome can grow right
            return size+2*std::min(left_potential,right_potential); //maximum size it can grow is the lesser of the two
        }
    };
    
    class Solution {
        //Defines a sub-palindrome we're searching
    public:
        bool *cp;
        Palindrome best;
        //calculates max potential size of palindrome given its position and the total string size
        //attempts to expand out the palindrome
        //returns the expanded palindrome if successful, otherwise the same palindrome
        Palindrome expand(const Palindrome& p, const char* s, int n)
        {
            Palindrome ep = p;
            int max_size = p.potential(n);
            for(int i=0; i<max_size && ep.start > 0; ++i)
            {
                if (s[ep.start-1] != s[ep.start+ep.size]) break; //not a match
                --ep.start; ep.size+=2;
            }
            return ep;
        }
        string longestPalindrome(string s) {
            auto cs = s.c_str(); //we want the string as a char array to iterate and do comparisons
            //catch trivial edges
            if (!s.size()) return ""; //if empty, return empty string
            else if (s.size() == 1) return s; //if size 1, it is by default a palindrome
            else if ((s.size() == 2) && cs[0] == cs[1]) return s; //if size 2 and they match, it's the minimal even palindrome
            else if ((s.size() == 3)) //minimal odd or left or right hand minimal even
            {
                if (cs[0] == cs[2]) return s; //if size 3 and they match, it's the minimal odd palindrome
                else if (cs[0] == cs[1]) return std::string(&cs[0],2); //catch the left hand minimal even palindrome
                else if (cs[1] == cs[2]) return std::string(&cs[1],2); //catch the right hand minimal even palindrome
            }
            int N = s.size(); //size of our string
            int start_idx = N/2; //starting index. Note, it's not -1 because we're mirroring on both sides anyways
            
            for(int i=start_idx; i<N-1; i++) //we stop at N-1 because at that point, there's no palindrome
            {
                Palindrome odd(i-1,3);
                Palindrome even(i,2);
                int odd_potential = odd.potential(N);
                int even_potential = even.potential(N);
                //if our current max potential is worse than our best, we're done
                if (std::max(odd_potential,even_potential) < best.size) break;
                
                //check if we have an odd palindrome by checking left and right of us
                if (cs[i-1] == cs[i+1]) //we have a minimal odd palindrome!
                {
                    //check if we can expand it
                    auto ep = expand(odd,cs,N);
                    if (ep.size > best.size) best = ep; //we found a current best
                }
                //check if we have an odd palindrome on the mirror side
                if (cs[N-i-2] == cs[N-i])
                {
                    Palindrome p(N-i-2,3);
                    auto ep = expand(p,cs,N);
                    if (ep.size > best.size) best = ep;
                }
                //check if we have an even palindrome by checking right of us
                if (cs[i] == cs[i+1])
                {
                    auto ep = expand(even,cs,N);
                    if (ep.size > best.size) best = ep;
                }
                //check if we have an even palindrome on the mirror side
                if (cs[N-i-1] == cs[N-i])
                {
                    Palindrome p(N-i-1,2);
                    auto ep = expand(p,cs,N);
                    if (ep.size > best.size) best = ep;
                }
            }
            if (best.size == 0) return std::string(1,cs[0]); //we didn't find one and it's not empty so just return a letter
            return std::string(cs+best.start,(size_t)best.size);
        }
    };
    

Log in to reply
 

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