Readable C++ solution, 6ms


  • 0
    L
    // There are basically two tricks here:
    // 1. Check for palindrome by starting at middle and expanding to both sides (using half-indices to start "between" two chars).
    // 2. Start the search at the middle of the string, as it has most potential of finding the longest palindrome, and quite early as soon as it's not possible to find a longer palindrome anymore.
    
    // String:         b   a   b   a   d
    // Half-indices:   0 1 2 3 4 5 6 7 8
    // Actual indices: 0   1   2   3   4
    
    // String:         c   b   b   d
    // Half-indices:   0 1 2 3 4 5 6
    // Actual indices: 0   1   2   3
    
    class Solution {
    public:
        string longestPalindrome(string s) {
            string longest = "";
    
            // Start at the middle, then circle.
            const int middle = s.size()-1;
            for (int delta = 0, direction = 1 ;  ; delta += direction == -1 ? 1 : 0, direction *= -1) {
                const int half_idx = middle + delta*direction;
    
                // stop early if not possible to get longer anymore.
                const int longest_possible = s.size() - delta;
                if (longest.size() >= longest_possible) break;
    
                string palin = expandPalindrome(s, half_idx);
                if (palin.size() > longest.size()) {
                    longest = palin;
                }
    
                // Done.
                if (half_idx == 0) break;
            }
            return longest;
        }
        
        static string expandPalindrome(const string& s, int half_idx) {
            int left = half_idx/2;
            int right = (half_idx+1)/2;
            if (s[left] != s[right]) {
                return "";
            }
            while (s[left] == s[right]) {
                left--; right++;
    
                // We are the largest palindrome we can become at this location.
                if (-1 == left || right == s.size()) {
                    break;
                }
            }
            return string(s, left+1, right-left-1);
        }
    };
    

Log in to reply
 

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