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.

Analysis: 想到了Naive的方法，时间复杂度为O(N^3)，知道肯定不是最优的方法，一时也想不出别的方法，于是看了网上的做法，最后采纳了这个人的方法，感觉他讲的比较全面：http://www.programcreek.com/2013/12/leetcode-solution-of-longest-palindromic-substring-java/

1. Naive Approach:  The time complexity is O(n^3). If this is submitted to LeetCode onlinejudge, "Time Limit Exceeded".

2. Dynamic Programming: 

Let s be the input string, i and j are two indices of the string.

Define a 2-dimension array "table" and let table[i][j] denote whether substring from i to j is palindrome.

Start condition:

table[i][i] == 1;table[i][i+1] == 1  => s.charAt(i) == s.charAt(i+1) 

Changing condition:

table[i][j] == 1 => table[i+1][j-1] == 1 && s.charAt(i) == s.charAt(j)

Time O(n^2) Space O(n^2)

3. Smart Algorithm: Time O(n^2), Space O(1)

 1 public class Solution { 2     public String longestPalindrome(String s) { 3         if (s == null || s.length() == 0) return null; 4         if (s.length() == 1) return s; 5         String longest = ""; 6         for (int i = 0; i < s.length(); i++) { 7             String temp = helper(s, i, i); 8             if (temp.length() > longest.length()) { 9                 longest = temp;10             }11             temp = helper(s, i, i + 1);12             if (temp.length() > longest.length()) {13                 longest = temp;14             }15         }16         return longest;17     }18     19     public String helper(String s, int start, int end) {20         while (start >=0 && end < s.length() && s.charAt(start) == s.charAt(end)) {21             start--;22             end++;23         }24         start++;25         end--;26         return s.substring(start, end + 1);27     }28 }