Accepted 3ms c++ solution with completed comments.


  • 0
    L
        string longestPalindrome(string s) 
        {
            // simple case
            if (s.length() <= 1)
                return s;
                
            const int strLen = s.length();
            int maxLength = 0;
            int startIdx = 0;
            int endIdx = 0;
    
            // for every characters...
            for (int i=0; i<strLen;)  {
                int l, r; // left and right index
       
                // init left and right position, and we're going to move left/right index if there's any
                // character which is the same as the current one.
                l = r = i;
    
                // move left point if there's any duplicated characters on the left side
                while (l-1>=0 && s[l]==s[l-1]) {
                    l--;
                }
                // move right point if there's any duplicated characters on the right side
                while (r+1<strLen && s[r]==s[r+1]) {
                    r++;
                }
                // move the current index base on right index, ignore duplicated characters.
                i = r+1; 
    
                // based on [left, right], expend search patterns, including the current one.
                // e.g.: abbbx --> bbb
                while(l>=0 && r<strLen) {
                    // character is the same, it's palindromic.
                    if (s[l]==s[r]) {
                        int currLength = (r-l+1); // the current sub string length
                        // if current length is greater than the maximum,
                        // update maximum length, and saving the start/end index.
                        if (currLength > maxLength) {
                            maxLength = currLength;
                            startIdx = l;
                            endIdx = r;
                        }
                        // move left, and right
                        l--;
                        r++;
                    }
                    else
                        break; // not a palindromic string anymore, break loop
                } // while
    
                // check the current index, if the remains characters is less than (or equals to)
                // the 50% of maximum length, no need to find anymore.
                if (strLen-i <= maxLength/2)
                    break;
            }//for
    
            return s.substr(startIdx, endIdx-startIdx+1);
        }
    

Log in to reply
 

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