Longest Palindrome Substring

• Lintcode : 200 / Leetcode 5
• Level : Medium

Problem

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Example
Example 1:

Input:"abcdzdcab"
Output:"cdzdc"
Example 2:

Input:"aba"
Output:"aba"
Challenge
O(n2) time is acceptable. Can you do it in O(n) time.

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O(n ^ 2)
space: O(1)

Answer

class Solution {
public:
    string longestPalindrome(string &s) {
        int len = s.size();
        int maxLen = INT_MIN;
        string ans;
        for (int i = 0; i < len; i++) {
            // center in the middle of char
            int l = isPalindrome(s, i, i);
            if (maxLen < l) {
                ans = s.substr(i - (l - 1) / 2, l); 
                maxLen = l;
            }
            l = isPalindrome(s, i, i + 1);
            // center in the char
            if (maxLen < l) {
                ans = s.substr(i - (l - 2) / 2, l);   
                maxLen = l;
            }
        }
        return ans;
    }
    int isPalindrome(string &s, int l, int r) {
        while (l >= 0 && r < s.size() && s[l] == s[r]) {
            l--, r++;
        }
        return r - l - 1;
    }
};
class Solution {
public:
    int longestPalindrome(string &s) {
        unordered_map<char, int> count;
        bool hasOdd = false; 
        for(auto i : s) {
            count[i]++;
        }
        int length = 0;
        for (auto it = count.begin(); it != count.end(); it++) {
            if (it -> second % 2)  {
                hasOdd = true;
                length += it -> second - 1;
            }else {
                length += it -> second;
            }
        }
        return hasOdd ? length + 1 : length;
    }
};

tags: string

​