LeetCode 5 - Longest Palindromic Substring
Longest Palindromic Substring | Set 2 | GeeksforGeeks
Given a string, find the longest substring which is palindrome. For example, if the given string is “forgeeksskeegfor”, the output should be “geeksskeeg”.
We can find the longest palindrome substring in (n^2) time with O(1) extra space. The idea is to generate all even length and odd length palindromes and keep track of the longest palindrome seen so far.
Fix a centre and expand in both directions for longer palindromes.
Step to generate even length palindrome
Fix two centre ( low and high ) and expand in both directions for longer palindromes.
DP:
http://www.geeksforgeeks.org/longest-palindrome-substring-set-1/
The value of table[i][j] is true, if the substring is palindrome, otherwise false. To calculate table[i][j], we first check the value of table[i+1][j-1], if the value is true and str[i] is same as str[j], then we make table[i][j] true. Otherwise, the value of table[i][j] is made false.
http://n1b-algo.blogspot.com/2009/01/longest-monotone-sequence-and.html
The trivial solution is to check if a palindrom of all possible size starts from a given index. For a index i in array, the possible possitions to test are i < j <= n. Total time taken = O(n^3). We can solve this problem using Longest Common Substring and suffix trees to solve this problem in O(n) time.
http://shirleyisnotageek.blogspot.com/2014/12/longest-palindromic-substring-dp-on.html
The complete explanation of this O(n) solution, which is called, Manacher's Algorithm can be found here. I will just simplify it based on my understanding.
So consider we have a string s = "aabab". How can we check every substring using iteration? We need to check "aa", "aab", "aaba", "aabab", then "aba" ... and so on. Then this will be O(n^2), we are not doing anything better. But, what if we add something into the string:
# a # a # b # a # b #
0 1 2 3 4 5 6 7 8 9 10
Well, whatever symbol you would like to use is fine. The point is, now we double the length of the string, and every substring of s is symmetric in the new string. If we want to check "aa", it is symmetric against "#", "aba" is symmetric against "b". Thus, by iterate through the new string, we can check every substring of s in linear time.
Read full article from Longest Palindromic Substring | Set 2 | GeeksforGeeks
Longest Palindromic Substring | Set 2 | GeeksforGeeks
Given a string, find the longest substring which is palindrome. For example, if the given string is “forgeeksskeegfor”, the output should be “geeksskeeg”.
We can find the longest palindrome substring in (n^2) time with O(1) extra space. The idea is to generate all even length and odd length palindromes and keep track of the longest palindrome seen so far.
Time complexity: O ( n^2 ) where n is the length of input string.
Auxiliary Space: O ( 1 )
Step to generate odd length palindrome:Auxiliary Space: O ( 1 )
Fix a centre and expand in both directions for longer palindromes.
Step to generate even length palindrome
Fix two centre ( low and high ) and expand in both directions for longer palindromes.
int longestPalSubstr(char *str){ int maxLength = 1; // The result (length of LPS) int start = 0; int len = strlen(str); int low, high; // One by one consider every character as center point of // even and length palindromes for (int i = 1; i < len; ++i) { // Find the longest even length palindrome with center points // as i-1 and i. low = i - 1; high = i; while (low >= 0 && high < len && str[low] == str[high]) { if (high - low + 1 > maxLength) { start = low; maxLength = high - low + 1; } --low; ++high; } // Find the longest odd length palindrome with center // point as i low = i - 1; high = i + 1; while (low >= 0 && high < len && str[low] == str[high]) { if (high - low + 1 > maxLength) { start = low; maxLength = high - low + 1; } --low; ++high; } } printf("Longest palindrome substring is: "); printSubStr(str, start, start + maxLength - 1); return maxLength;}http://www.geeksforgeeks.org/longest-palindrome-substring-set-1/
The value of table[i][j] is true, if the substring is palindrome, otherwise false. To calculate table[i][j], we first check the value of table[i+1][j-1], if the value is true and str[i] is same as str[j], then we make table[i][j] true. Otherwise, the value of table[i][j] is made false.
Time complexity: O ( n^2 )
Auxiliary Space: O ( n^2 )
Auxiliary Space: O ( n^2 )
int longestPalSubstr( char *str ){ int n = strlen( str ); // get length of input string // table[i][j] will be false if substring str[i..j] // is not palindrome. // Else table[i][j] will be true bool table[n][n]; memset(table, 0, sizeof(table)); // All substrings of length 1 are palindromes int maxLength = 1; for (int i = 0; i < n; ++i) table[i][i] = true; // check for sub-string of length 2. int start = 0; for (int i = 0; i < n-1; ++i) { if (str[i] == str[i+1]) { table[i][i+1] = true; start = i; maxLength = 2; } } // Check for lengths greater than 2. k is length // of substring for (int k = 3; k <= n; ++k) { // Fix the starting index for (int i = 0; i < n-k+1 ; ++i) { // Get the ending index of substring from // starting index i and length k int j = i + k - 1; // checking for sub-string from ith index to // jth index iff str[i+1] to str[j-1] is a // palindrome if (table[i+1][j-1] && str[i] == str[j]) { table[i][j] = true; if (k > maxLength) { start = i; maxLength = k; } } } } printf("Longest palindrome substring is: "); printSubStr( str, start, start + maxLength - 1 ); return maxLength; // return length of LPS}http://n1b-algo.blogspot.com/2009/01/longest-monotone-sequence-and.html
The trivial solution is to check if a palindrom of all possible size starts from a given index. For a index i in array, the possible possitions to test are i < j <= n. Total time taken = O(n^3). We can solve this problem using Longest Common Substring and suffix trees to solve this problem in O(n) time.
http://shirleyisnotageek.blogspot.com/2014/12/longest-palindromic-substring-dp-on.html
public String longestPalindrome(String s) { if (s == null || s.length() == 0) return ""; String rst = s.substring(0,1); int maxSubstring = 1; boolean[][] palindrome = new boolean[s.length()][s.length()]; for (int i = 0; i < s.length(); i++) { palindrome[i][i] = true; } for (int len = 1; len < s.length(); len++) { for (int i = 0; i + len < s.length() ; i++) { if (len < 2) { palindrome[i][i + len] = (s.charAt(i) == s.charAt(i + len)); } else { palindrome[i][i + len] = palindrome[i + 1][i + len - 1] && (s.charAt(i) == s.charAt(i + len)); } if (palindrome[i][i + len] && (len + 1 > maxSubstring)){ maxSubstring = len + 1; rst = s.substring(i, i + len + 1); } } } return rst; }So consider we have a string s = "aabab". How can we check every substring using iteration? We need to check "aa", "aab", "aaba", "aabab", then "aba" ... and so on. Then this will be O(n^2), we are not doing anything better. But, what if we add something into the string:
# a # a # b # a # b #
0 1 2 3 4 5 6 7 8 9 10
Well, whatever symbol you would like to use is fine. The point is, now we double the length of the string, and every substring of s is symmetric in the new string. If we want to check "aa", it is symmetric against "#", "aba" is symmetric against "b". Thus, by iterate through the new string, we can check every substring of s in linear time.
public String longestPalindrome(String s) { if (s == null || s.length() == 0) return ""; int maxSubstring = 1; String rst = s.substring(0, 1); for (int i = 1; i <= 2 * s.length() - 1; i++) { int count = 1; while (i - count >= 0 && i + count <= 2 * s.length() && get(s, i - count) == get(s, i + count)) { count++; } //Note that since "#" always equals "#", we will have an extra count for each substring count--; if (count > maxSubstring) { maxSubstring = count; rst = s.substring((i - count) / 2, (i + count) / 2); } } return rst; } private char get(String s, int index) { if (index % 2 == 0) return '#'; else return s.charAt(index / 2); }