LeetCode - Longest Palindromic Substring | Darren's Blog

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 isO(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);

}

• 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(n2) time and O(1) space is achieved.

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.

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.
Read full article from LeetCode - Longest Palindromic Substring | Darren's Blog