C++ With Trick To Make Checking Odd/Even Length Palindromes Easier


  • 0
    F
    class Solution {
    public:
        string longestPalindrome(string s) {
            // make it easier to check without worrying about odd/even pal lengths
            string palChecker("\n");
            for(auto ch : s){
                palChecker += ch;
                palChecker += "\n";
            }
            int maxResultLen = 0;
            int mid = palChecker.length() / 2;
            int resultStart, resultStop, resultLen;
            int answerStart, answerStop;
            findAtIndex(palChecker, mid, answerStart, answerStop, resultLen);
            maxResultLen = answerStop-answerStart;
    
            for(int i = mid-1, j = mid+1; i >= 0 || j < palChecker.length(); --i, ++j){
    
                if((i*2) < maxResultLen && 2*(palChecker.length()-j) < maxResultLen) break;
                
                findAtIndex(palChecker, i, resultStart, resultStop, resultLen);
                if(resultLen >= maxResultLen){
                    answerStart = resultStart;
                    answerStop = resultStop;
                    maxResultLen = resultLen;
                }
                findAtIndex(palChecker, j, resultStart, resultStop, resultLen);
                if(resultLen >= maxResultLen){
                    answerStart = resultStart;
                    answerStop = resultStop;
                    maxResultLen = resultLen;
                }
            }
            string finalResult;
            for(int i = answerStart; i <= answerStop; ++i){
                if(palChecker[i] != '\n') finalResult += palChecker[i];
            }
            return finalResult;
        }
        
        void findAtIndex(string &s, int index, int &start, int &stop, int &len){
            len = 0;
            start = 0;
            stop = 0;
    
            for(int i = index-1, j = index + 1; i >= 0 && j < s.length(); --i, ++j){
                start = i;
                stop = j;
                len = (stop-start);
                if(s[i] != s[j]){
                    ++start;
                    --stop;
                    len = (stop-start);
                    return;
                }
            }
        }
    };
    
    

Log in to reply
 

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