Massive Algorithms: LeetCode 5 - Longest Palindromic Substring

LeetCode 5 - Longest Palindromic Substring

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.
Brute Force: Enumerate every possible substring, and verify whether it is palindromic. The number of possible subtrings is

C(n,2)=O(n2) , and verifying each substring takes

O(n) time. As a result, its time complexity is

O(n3)

public String longestPalindrome(String s) {

    int length = s.length();

    int longestStart = 0, longestEnd = 0;

    // Enumerate every possible substring with start index i and end index j

    for (int i = 0; i < length; i++) {

        for (int j = i; j < length; j++) {

            // s_i...s_j is a palindrome of longer length

            if (isPalindromic(s, i, j) && j-i > longestEnd-longestStart) {

                longestStart = i;

                longestEnd = j;

}

}

}

    return s.substring(longestStart, longestEnd+1);

}

Dynamic Programming: Let

p[i,j] denote whether the substring

Si…Sj is palindromic. It can be observed that

p[i,j] is true if and only if

p[i+1,j−1] is true and

Si=Sj . The base cases for this recursion are that

p[i,i] is true and that

p[i,i+1] is true if and only if

Si=Si+1

public String longestPalindrome(String s) {

    int n = s.length();

    int longestLength = 1, longestStart = 0;

    // Create and initialize the table 

    boolean[][] p = new boolean[n][n];

    for (int i = 0; i < n; i++)

        p[i][i] = true;         // s_i is a palindrome

    for (int i = 0; i < n-1; i++) {

        // s_i,s_{i+1} is a palindrome iff s_i == s_{i+1}

        if (s.charAt(i) == s.charAt(i+1)) {

            p[i][i+1] = true;

            longestLength = 2;

            longestStart = i;

}

}

    // Fill the table by ascending order of substring length

    for (int len = 3; len <= n; len++) {

        for (int i = 0; i < n-len+1; i++) {

            int j = i + len - 1;

            // s_i...s_j is a palindrome iff s_{i+1}...s_{j-1} is palindrome and s_i == s_j

            if (p[i+1][j-1] && s.charAt(i) == s.charAt(j)) {

                p[i][j] = true;

                longestLength = len;

                longestStart = i;

}

}

}

    return s.substring(longestStart, longestStart+longestLength);

}

https://discuss.leetcode.com/topic/25500/share-my-java-solution-using-dynamic-programming

dp(i, j) represents whether s(i ... j) can form a palindromic substring, dp(i, j) is true when s(i) equals to s(j) and s(i+1 ... j-1) is a palindromic substring. When we found a palindrome, check if it's the longest one. Time complexity O(n^2).

public String longestPalindrome(String s) {
  int n = s.length();
  String res = null;
    
  boolean[][] dp = new boolean[n][n];
    
  for (int i = n - 1; i >= 0; i--) {
    for (int j = i; j < n; j++) {
      dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1]);
            
      if (dp[i][j] && (res == null || j - i + 1 > res.length())) {
        res = s.substring(i, j + 1);
      }
    }
  }
    
  return res;
}

http://www.zrzahid.com/longest-palindromic-substring-in-on2-time/

DP solution
The above algorithm actually does some extra computation than O(n^2). We can do dynamic programming to cache some computation.

Let, LeOPT(i,j) be the maximum length of palindromes considering in the input array A from i to j.

OPT(i,j) = 2 + OPT(i+1, j-1) if A[i] = A[j],
         = max (OPT(i,j-1), OPT(i+1,j), otherwise.

public static int longestPalindromDP(String str){
 int n = str.length();
 int dp[][] = new int[n+1][n+1];
 for(int i = 1; i<n; i++){
  dp[i][i] = 1;
 }
 
 //find palindrom of each possible length
 for(int len = 2; len <= n; len++){
  //try to get a palindrom of length len starting at each position i
  for(int i = 1; i <= n-len+1; i++){
   //right end position of current palindrom
   int j = i+len-1;
   
   if(str.charAt(i-1) == str.charAt(j-1)){
    dp[i][j] = 2+dp[i+1][j-1];
   }
   else{
    dp[i][j] = Math.max(dp[i][j-1], dp[i+1][j]);
   }
  }
 }
 
 return dp[1][n];
}

Center Expansion: We observe that a palindrome mirrors around its center. Therefore, a palindrome can be expanded from its center. Note that 2n−1centers is available, considering the ones between two adjacent characters. As such, O(n^2) time and O(1) space is achieved.

https://leetcode.com/articles/longest-palindromic-substring/

In fact, we could solve it in

O(n^2)

time using only constant space.

We observe that a palindrome mirrors around its center. Therefore, a palindrome can be expanded from its center, and there are only

2n - 1

such centers.

You might be asking why there are

2n - 1

but not

n

centers? The reason is the center of a palindrome can be in between two letters. Such palindromes have even number of letters (such as

''abba''

) and its center are between the two

'b'

public String longestPalindrome(String s) {
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        int len1 = expandAroundCenter(s, i, i);
        int len2 = expandAroundCenter(s, i, i + 1);
        int len = Math.max(len1, len2);
        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return s.substring(start, end + 1);
}

private int expandAroundCenter(String s, int left, int right) {
    int L = left, R = right;
    while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
        L--;
        R++;
    }
    return R - L - 1;
}

https://discuss.leetcode.com/topic/23498/very-simple-clean-java-solution
https://discuss.leetcode.com/topic/8219/easy-java-solution-with-o-1-space-and-o-n-2-time

private int lo, maxLen;

public String longestPalindrome(String s) {
 int len = s.length();
 if (len < 2)
  return s;
 
    for (int i = 0; i < len-1; i++) {
      extendPalindrome(s, i, i);  //assume odd length, try to extend Palindrome as possible
      extendPalindrome(s, i, i+1); //assume even length.
    }
    return s.substring(lo, lo + maxLen);
}

private void extendPalindrome(String s, int j, int k) {
 while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
  j--;
  k++;
 }
 if (maxLen < k - j - 1) {
  lo = j + 1;
  maxLen = k - j - 1;
 }
}

Code from http://leetcode.com/2011/11/longest-palindromic-substring-part-i.html

string expandAroundCenter(string s, int c1, int c2) {

  int l = c1, r = c2;

  int n = s.length();

  while (l >= 0 && r <= n-1 && s[l] == s[r]) {

    l--;

    r++;

}

  return s.substr(l+1, r-l-1);

}

string longestPalindromeSimple(string s) {

  int n = s.length();

  if (n == 0) return "";

  string longest = s.substr(0, 1);  // a single char itself is a palindrome

  for (int i = 0; i < n-1; i++) {

    string p1 = expandAroundCenter(s, i, i);

    if (p1.length() > longest.length())

      longest = p1;

    string p2 = expandAroundCenter(s, i, i+1);

    if (p2.length() > longest.length())

      longest = p2;

}

  return longest;

}

Manacher’s Algorithm: It takes advantages of palindrome's symmetric property and avoids some unnecessary computations.
http://segmentfault.com/a/1190000002991199
Manacher算法是非常经典的计算连续下标回文的算法。它利用了回文的对称性，更具体的来说，是回文内回文的对称
http://www.felix021.com/blog/read.php?2040
首先用一个非常巧妙的方式，将所有可能的奇数/偶数长度的回文子串都转换成了奇数长度：在每个字符的两边都插入一个特殊的符号。比如 abba 变成 #a#b#b#a#， aba变成 #a#b#a#。为了进一步减少编码的复杂度，可以在字符串的开始加入另一个特殊字符，这样就不用特殊处理越界问题

    public String longestPalindrome(String s) {
        if(s.length()<=1){
            return s;
        }
        // 预处理字符串，避免奇偶问题
        String str = preProcess(s);
        // idx是当前能够向右延伸的最远的回文串中心点，随着迭代而更新
        // max是当前最长回文串在总字符串中所能延伸到的最右端的位置
        // maxIdx是当前已知的最长回文串中心点
        // maxSpan是当前已知的最长回文串向左或向右能延伸的长度
        int idx = 0, max = 0;
        int maxIdx = 0;
        int maxSpan = 0;
        int[] p = new int[str.length()];
        for(int curr = 1; curr < str.length(); curr++){
            // 找出当前下标相对于idx的对称点
            int symmetryOfCurr = 2 * idx - curr;
            // 如果当前已知延伸的最右端大于当前下标，我们可以用对称点的P值，否则记为1等待检查
            p[curr] = max > curr? Math.min(p[symmetryOfCurr], max - curr):1;
            // 检查并更新当前下标为中心的回文串最远延伸的长度
            while((curr+p[curr])<str.length() && str.charAt(curr+p[curr])==str.charAt(curr-p[curr])){
                p[curr]++;
            }
            // 检查并更新当前已知能够延伸最远的回文串信息
            if(curr+p[curr]>max){
                max = p[curr] + curr;
                idx = curr;
            }
            // 检查并更新当前已知的最长回文串信息
            if(p[curr]>maxSpan){
                maxSpan = p[curr];
                maxIdx = curr;
            }
        }
        //去除占位符
        return s.substring((maxIdx-maxSpan)/2,(maxSpan+maxIdx)/2-1);
    }

    private String preProcess(String s){
        // 如ABC,变为$#A#B#C#
        StringBuilder sb = new StringBuilder();
        sb.append("$");
        for(int i = 0; i < s.length(); i++){
            sb.append("#");
            sb.append(s.charAt(i));
        }
        sb.append("#");
        return sb.toString();
    }

public String longestPalindrome(String s) {

    String t = preProcess(s);

    int n = t.length();

    int[] p = new int[n];

    int center = 0, right = 0;

    for (int i = 1; i < n-1; i++) {

        int mirror = 2 * center - i;

        p[i] = (right > i) ? Math.min(right-i, p[mirror]) : 0;

        // Attempt to expand the palindrome centered at index i

        while (t.charAt(i+p[i]+1) == t.charAt(i-p[i]-1))

            p[i]++;

        // Adjust center and right edge if necessary

        if (i + p[i] > right) {

            center = i;

            right = i + p[i];

}

}

    // Find the length of the longest palindrome, and the start index of it

    int longestLength = 0, longestStart = 0;

    for (int i = 1; i< n-1; i++) {

        if (p[i] > longestLength) {

            longestLength = p[i];

            longestStart = (i-1-longestLength) / 2;

}

}

    return s.substring(longestStart, longestStart+longestLength);

}

// Add "#" betweeen characters,

// and "^" and "$" as the start and end sntinels, respectively

private String preProcess(String s) {

    int n = s.length();

    if (n == 0)

        return "^$";

    String result = "^";

    for (int i = 0; i < n; i++)

        result += "#" + s.charAt(i);

    result += "#$";

    return result;

}

Suffix Trees: As said in the Wikipedia page, there exists a linear solution base on suffix trees, which I have not investigated yet.

X. https://discuss.leetcode.com/topic/21848/ac-relatively-short-and-very-clear-java-solution

Key idea, every time we move to right, we only need to consider whether using this new character as tail could produce new palindrome string of length (current length +1) or (current length +2)

Example: "xxxbcbxxxxxa", (x is random character, not all x are equal) now we 
          are dealing with the last character 'a'. The current longest palindrome
          is "bcb" with length 3.
1. check "xxxxa" so if it is palindrome we could get a new palindrome of length 5.
2. check "xxxa" so if it is palindrome we could get a new palindrome of length 4.
3. do NOT check "xxa" or any shorter string since the length of the new string is 
   no bigger than current longest length.
4. do NOT check "xxxxxa" or any longer string because if "xxxxxa" is palindrome 
   then "xxxx" got  from cutting off the head and tail is also palindrom. It has 
   length > 3 which is impossible.'

    public String longestPalindrome(String s) {
        String res = "";
        int currLength = 0;
        for(int i=0;i<s.length();i++){
            if(isPalindrome(s,i-currLength-1,i)){
                res = s.substring(i-currLength-1,i+1);
                currLength = currLength+2;
            }
            else if(isPalindrome(s,i-currLength,i)){
                res = s.substring(i-currLength,i+1);
                currLength = currLength+1;
            }
        }
        return res;
    }
    
    public boolean isPalindrome(String s, int begin, int end){
        if(begin<0) return false;
        while(begin<end){
         if(s.charAt(begin++)!=s.charAt(end--)) return false;
        }
        return true;
    }

https://en.wikipedia.org/wiki/Longest_palindromic_substring
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.

Also check http://www.geeksforgeeks.org/longest-palindrome-substring-set-1/
Longest Palindromic Substring: Center Expansion and DP: n^2
http://massivealgorithms.blogspot.com/2014/07/dynamic-programming-set-12-longest.html
Read full article from LeetCode - Longest Palindromic Substring | Darren's Blog

LeetCode 5 - Longest Palindromic Substring

Labels

Popular Posts