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 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 SiSj is palindromic. It can be observed that p[i,j] is true if and only if p[i+1,j1] 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 2n1centers 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's.
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

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts