C++ O(N^2) solution, but VERY easy to understand!


  • 0

    This problem can be solved in O(N) time complexity, but the problem doesn't make it a condition. So here is the slower but very easy to understand O(N^2) time complexity solution with a O(1) space (i.e. no extra space needed). The idea is to expand around the center and return the longest palindrome. But the idea is to check (expand around) both even and odd length strings, since we don't know if the user will enter a string with a single character in the middle (odd length) or two characters in the middle (even).

    string expandAroundCenter(string s, int left, int right) {
        while (left>=0 && right<=s.length()-1 && s[left]==s[right]) {left--; right++;}
        return s.substr(left+1, right - (left+1)); //Return longest palindrome string only.
    }
    
    string longestPalindrome(string s) {
        if (s.length()==0) return "";
        string longest = s.substr(0,1); // Single char itself is a palindrome (use .substr() to get string).
        for(int i=0; i<s.length()-1; ++i) {
            string odd = expandAroundCenter(s, i, i); // If length is odd e.g. aba.
            string even = expandAroundCenter(s, i, i+1); // If length is even e.g. abba.
            if (odd.length() > longest.length()) longest = odd;
            if (even.length() > longest.length()) longest = even;
        }
        return longest;
    }
    

Log in to reply
 

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