Longest_Palindromic_ Sub_String

OK, Let’s continue….

Problem Statement:

Given a string s, find the longest palindromic sub string 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 One: Brute Force

Simple but not efficient. Iterate all possible sub string, then test whether it is a palindromic string. If it is, then check whether the length is longer than the cached longest length. It is so slow, almost useless.

	class Solution {
	public:
	bool isPalindrome(string &s)
	{
	int len = s.size();
	for(int i = 0; i< len/2; i++)
	{
	if(s[i] != s[len – i – 1])
	return false;
	}
	return true;
	}

	string longestPalindrome(string s) {
	int len = s.size();
	int iStart = 0, Max = 0;
	string temp;
	for(int i =0; i< len; i++)
	{
	for (int j = i; j < len ; j++)
	{
	temp = s.substr(i, j-i+1);
	if(isPalindrome(temp) && j-i + 1 > Max)
	{
	Max = j-i+1;
	iStart = i;
	}
	}
	}
	return s.substr(iStart, Max);
	}
	};

view raw

Longest_Palindromic_Substring_BF.cpp

hosted with ❤ by GitHub

Time Complexity: O(n^3)

Space Complexity: O(1)

Solution Two: Extension from Center

The general idea for this approach is to firstly select a center, and then extend from this center to check whether the sub string is palindromic. Since the longest palindromic string might have even or odd number of characters, so when we pick up the center, we should both pick each character (odd sub string) and the gap between each string (even sub string). As a result of this, the total number of iteration should be n + n – 1, which is 2*n – 1.

5_6

Each time when we make an extension, we check whether the new sub string is palindromic. If it is, we update the max length variable. If it is not, we move on. The code is pretty straightforward.

	class Solution {
	public:
	string longestPalindrome(string s) {
	int start = 0, end = 0;
	int len = 0;
	for(int i = 0; i< s.size(); i++)
	{
	int len1 = PalindromeLength(s, i, i);
	int len2 = PalindromeLength(s, i, i+1);
	len = max(len1, len2);
	if(len > end – start)
	{
	start = i – (len – 1)/2;
	end = i + len/2;
	}
	}
	return s.substr(start, end – start + 1);
	}

	int PalindromeLength(string &s, int Left, int Right)
	{
	int L = Left, R = Right;
	while(L>=0 && R< s.size() && s[L] == s[R])
	{
	L–;
	R++;
	}
	return R – L – 1;
	}
	};

view raw

Longest_Palindromic_Sub_String_ExtensionFromCenter.cpp

hosted with ❤ by GitHub

Time Complexity: O(n^2)

Space Complexity: O(1)

Solution Three: Optimized Brute Force

When we apply the brute force approach, we have to check every possible sub strings, but actually, we do not need to do every check if we cache some intermediate results. For example, if we already know that string [i+1, j-1] is a palindromic sub string, when we want to know whether [i, j] is a palindromic string, we only need to check whether s[i] == s[j].

5_3

This solution is not suitable when the sub string only contains one or two characters, since at that moment, i+1 is greater than j-1, which means we are not checking the correct sub string. We have to handle these two special cases when we run our algorithm.

	class Solution {
	public:
	string longestPalindrome(string s) {
	if(s == "")
	return s;
	int len = s.size();
	int maxsLen = 0;
	bool arr[len][len];
	string finalString;

	for(int i = 1; i <= len; i++)
	{
	for(int start = 0; start < len; start++)
	{
	int end = start + i – 1;
	if(end >= len)
	break;
	arr[start][end] = (i == 1 \|\| i == 2 \|\| arr[start + 1][end – 1])&&(s[start] == s[end]);
	if(arr[start][end] && i > maxsLen)
	{
	finalString = s.substr(start, i);
	maxsLen = i;
	}
	}
	}
	return finalString;
	}
	};

view raw

Longest_Palindromic_Sub_String_BFOpt.cpp

hosted with ❤ by GitHub

Time Complexity: O(n^2)

Space Complexity: O(n^2)

Solution Four: Manacher’s algorithm

This algorithm seems especially designed for this problem. Basically, it is a little bit similar to central extension algorithm, but more tricky.

First thing let’s try to do some processing to our original array. When we start analyzing this problem, we have stated that the number of elements affect the final algorithm. Here, we insert some new elements to the original string and convert this string to be a string which only contains odd number of elements.

The rule is to insert ‘^’ and ‘$’ character to the both ends of the string, and insert ‘#’ character to all the gaps between original characters (see the picture below). When we finish the insertion, we will get a string which only contains odd number of elements. And when we do the central extension algorithm like we discussed above, we can aways guarantee we will exit the loop when the comparison hits both ends (‘^’ != ‘$’, always true).

5_7

When the insertion is over, we can have another array P to store the number of elements which extend from the center, this number is also the number of characters from the original array, which are involved during the extension:

5_8

For example, when we see that P[6] is actually 5. Now if we consider P[6] is the center, then we can see it extends to both sides 5 unites (‘#’ from both sides are considered as the same characters) before the two sides have different characters. And this number 5 is also all the characters involved in the original array, which is c-b-c-b-c. Or we can say, 5 is the length of this palindromic sub string.

If we know this, we can easily calculate the original array index. The starting index of the original array should be:

(i – P[i]) / 2

For example, if 6 – P[6], it is 1, then divided by 2, the number is 0, which corresponds to the first element of the original array, which is c. And the length of the sub array is P[6] = 5.

OK, the next is the key part of Manacher’s algorithm. It utilizes the symmetric feature of palindromic strings. Look at the picture below, let’s mark

5_9

We can see here, C is the center, and R is the maximum radius of the palindromic sub string, we define R as R = C + P[i]. C and R are in the current palindromic sub string and R is the most right boundary.

So, how can we calculate P[i]? If we do the central extension algorithm, we can extend to both sides. But here, we can utilize the symmetric feature of palindromic string, let’s define i_mirror is a mirror index of i related to the center C, so the i_mirror = 2 * C – i. In the above example, P[i_mirror] = 3, since the palindromic string is symmetric, so P[i] should be 3 as well. However, there are some special cases we need to handle before we assign the value of P[i_mirror] to P[i]:

i + P[i] > R

In this case, when we try to assign value of P[i_mirror] to P[i], which is 7. We find that i + P[i] is greater than R, which is 22. Since R is the most right boundary of this palindromic sub string, if the P[i] + i > R, we cannot guarantee that all the right elements of the P[i] is indeed symmetric of its left part. The only thing we can guarantee is that elements i+1 to elements R should be symmetric to the left of P[i].

So, in this case, we have to assign P[i] = R – P[i] = 5. After that, we extend from R, and compare T[R+1] and T[R+1 symmetric to P[i]], if they are equal, we increase P[i]. Else we ignore.

5_10

P[i_mirror] is out of the left boundary

Look at the picture below, should we assign P[i] = 1? No, that’s because the P[i_mirror] hits the left boundary for a second iteration. However, for our P[i], we did not encounter any boundry, we should extend like the central extension algorithm. If we found more symmetric elements, we need to update P[i].

5_12

i equals R

First we set P[i] = 0; then we extend to both sides like before.

Whenever we have a larger boundary (P[i] + i > R) of P[i], we need to update C and R to the current palindromic string. Which means, we update:

C = P[i];

R = P[i] + i;

The reason we do this is because we need to guarantee that i is always inside boundary R.

For example, look at the picture below:

5_12

If we continue to calculate the P[i] now, the P[i] should finally become 10 + 3 = 13. (3 maximum symmetric elements, ‘#’ counts). We need to update R = 13, and C = 10. Then we continue our loop.

I hope I have explained all of the staff. Let’s look at the code:

	class Solution {
	public:
	string preProcess(string s)
	{
	int len = s.size();
	string proStr = "^";
	//string numberStr = "#";
	//string dollarStr = "$";

	for(int i = 0; i < len; i++)
	{
	proStr.push_back('#');
	proStr.push_back(s[i]);
	}
	proStr.push_back('#');
	proStr.push_back('$');

	return proStr;

	}

	string longestPalindrome(string s) {
	int len = s.size();
	if(len == 0)
	return s;
	string pS = preProcess(s);
	int len_pS = pS.size();
	int C = 0, R = 0, i_mirror = 0;
	int arr[len_pS];

	for(int i = 0; i < len_pS; i++)
	{
	i_mirror = 2 * C – i;

	if(i < R)
	{
	arr[i] = min(R – i, arr[i_mirror]);
	}
	else
	{
	arr[i] = 0;
	}

	while(pS[i+1 + arr[i]] == pS[i – 1 – arr[i]])
	{
	arr[i]++;
	}

	if(i + arr[i] > R)
	{
	C = i;
	R = i + arr[i];
	}
	}

	int maxLen = 0, start = 0;
	for(int i = 0; i < len_pS; i++)
	{
	if(arr[i]>maxLen){
	maxLen = arr[i];
	start = i;
	}
	}
	start = (start – maxLen)/2;
	return s.substr(start, maxLen);
	}
	};

view raw

Longest_Palindromic_Sub_String_Manecher.cpp

hosted with ❤ by GitHub

Basically, we need to handle all the three cases separately. Whenever i + P[i] > R, we update C and R. As for the time complexity, when the algorithm runs, all the characters are at maximum touched twice, one for the linear forward searching, one for T[R + i] == T[(R + i)mirror], so the time complexity should be approximately 2*n, which is O(n).

Time Complexity: O(n)

Space Complexity: O(n)

That’s all for this article….

共享此文章：

Like this:

Related

Leave a Reply Cancel reply