Algorithm Puzzles: Longest Palindromic Substring

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”

Solving

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:



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: