# LeetCode 5. Longest Palindromic Substring (Java)
###### tags: `leetcode` `Java` `Palindromic`

## Description
> Given a string s, return the longest palindromic substring in s.

>給定一個String，並找出最長的回文子字串（palindromic substring），如有多個相同長度的最長子字串可只回傳一個

## Example

Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Input: s = "cbbd"
Output: "bb"

Input: s = "ac"
Output: "a"

## Idea
- **Approach 1 暴力法**
+ 先用雙迴圈找出每組substring，時間複雜度為$O(n^2)$
+ 再將每組找出的substring測試是否為迴文，時間複雜度$O(n)$
+ 總共時間複雜度為$O(n^3)$，==無法處理過長字串，Leetcode因處理時間太長無法通過==
- **Approach 2**
+ ==如果一個迴文子字串，其中心不是回文，那這串子字串絕對不是回文==
+ 使用外迴圈遍歷字串中的每個字元，內迴圈在用兩個指標``start``和``end``以往外擴展
+ 因為會有奇偶數問題，所以內迴圈分成兩組分別處理
+ 總時間複雜度為$O(n^2)$，空間複雜度為$O(1)$
## Code
**Approach 1**

class Solution {
    public String longestPalindrome(String s) {
        //if(s.length() == 1) return s;        
        int len = s.length();
        String result = new String();
        int max_length = 0;
        for (int i = 0;i < len;i++){
            for (int j = i;j < len;j++){
                String ss = s.substring(i, j+1);
                boolean isPal = true;
                for (int z = 0; z < ss.length(); z++){
                    if(ss.charAt(z) != ss.charAt(ss.length()-z-1)){
                        isPal = false;
                        break;
                    }
                }
                if(isPal && ss.length() > max_length){
                    max_length = ss.length();
                    result = ss;
                }
                
            }
        }
        return result;
    }
}

我寫完此寫法後，因為執行時間過長導致Time Limit Exceeded，所以又找了其他方法，將Big-O變小

**Approach 2**

class Solution {
    public String longestPalindrome(String s) {      
        int len = s.length();
        String result = new String();
        int max_length = 0;
        for (int i = 0;i < len;i++){ 
            //center odd
            
            for (int start = i, end = i; start >= 0 && end < len;start--,end++){
                if(s.charAt(start) != s.charAt(end))//判斷前後是否一致
                    break; //不一致的話就不是回文，跳出迴圈
                if(end - start + 1 > max_length){ //檢查此次的回文子字串是否為最長的
                    max_length = end - start + 1;
                    result = s.substring(start, end+1);//將此子字串放到result
                }
            }
            //center even
            
            for (int start = i, end = i+1; start >= 0 && end < len;start--,end++){
                //因為考慮到會有偶數的子字串(ex.cbbc)所以end在初始就往右一格或start往左一格都可
                if(s.charAt(start) != s.charAt(end))
                    break;   
                if(end - start + 1 > max_length){
                    max_length = end - start + 1;
                    result = s.substring(start, end+1);
                }
            }
        }
        return result;
    }
}

## Result (Approach 2)
Runtime: **28** ms, faster than **57.01%** of Java online submissions for Longest Palindromic Substring.
Memory Usage: **39.6** MB, less than **44.91%** of Java online submissions for Longest Palindromic Substring.