Algorithm Puzzles everyday every week sometimes: Longest Palindromic Substring
Puzzle
Puzzle from leetcode:
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: “babad”
Output: “bab”
Note: “aba” is also a valid answer.
Example 2:
Input: “cbbd”
Output: “bb”
Solution
First Came out solution:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
 class Solution { public: string longestPalindrome(const string& s) { int head = 0,tail = 0; int length = s.length(); int longestH = 0, longestT = 0; while(head != length){ if(s[head] == s[tail]){ if(isPalindromic(s.substr(head, tail  head + 1))){ longestH = head; longestT = tail; } } ++tail; if(tail >= length){ ++head; tail = head + longestT  longestH + 1; if(tail >= length){ break; } } } return s.substr(longestH, longestT  longestH + 1); } private: bool isPalindromic(const string& s){ double dMid = s.length()/2.0; int mid = s.length()/2; string sub = s.substr((dMid  mid) > 0 ? mid + 1 : mid); std::reverse(sub.begin(), sub.end()); if(sub == s.substr(0, mid)){ return true; } return false; } };

Result:
![](/2019/08/04/AlgorithmPuzzlesLongestPalindromicSubstring/f1.jpeg)
Well, that’s the worst result I have ever seen.
Extend from the center
Checked the solution provided by leetcode, there is one way only have time complexity O(n²), I implemented in it C++ with a little optimization:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
 class Solution { public: const string longestPalindrome(const string& s) { int start = 0, maxLength = 0, halfLength = 0; for(int i = 0; i < s.length(); i++){ if(s.length()  i + 1 < halfLength  i + 1 < halfLength){ continue; } int len1 = extendFromCenter(s, i, i); int len2 = extendFromCenter(s, i, i+1); int len = len1 > len2 ? len1 : len2; if(len > maxLength){ start = i  (len  1) / 2; maxLength = len; halfLength = maxLength / 2; } } return s.substr(start, maxLength); } private: int extendFromCenter(const string& s, int left, int right){ while(left >= 0 && right < s.length() && s[left] == s[right]){ left; ++right; } return right  left  1; } };

Result with this: