> For the complete documentation index, see [llms.txt](https://jenhsuan.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jenhsuan.gitbook.io/algorithm/leetcode/5.-longest-palindromic-substring.md).

# 5. Longest Palindromic Substring

## 1.問題

* 給予一個字串, 找出長度最長的回文字串, 可以假設最長的字串長度為1000

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LLISrl_1VRJ0HMig2lv%2F-LLJFvr9u07vUeBAO8cS%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-09-01%20%E4%B8%8B%E5%8D%884.32.50.png?alt=media\&token=f6c42659-8a2a-4671-a181-cdf9a5d637ac)

## 2.想法

* 提問: 字串是否可以是0
* function header, parameter, return value
* example input
* 說明想法
  * 移動罩窗, 以每個字元為中心, 有奇數罩窗與偶數罩窗兩個case, 如果left == right, 則繼續擴大罩窗, 不然就回傳sub string
  * 注意c++ 取substring的用法
* 測試
* 計算複雜度: O(n)?

## 3.程式碼

```
class Solution {
public:
    string longestPalindrome(string s) {
        int size = s.length();
        string res("");
        if (size == 0 || size == 1) {
            return s;
        }
        for (int i = 0; i< size - 1; i++) {
            //奇數
            string odd = getMaxPalindrome(s, i, i); 
            if (odd.length() > res.length()) {
                res = odd;
            }
            //偶數
            string even = getMaxPalindrome(s, i, i + 1);
            if (even.length() > res.length()) {
                res = even;
            }
        }
        return res;
    }
private:
    string getMaxPalindrome(string s, int left, int right) {
        while (left < s.size() && 
               right >= 0 &&
               s[left] == s[right]) {
            right++;
            left--;
        }
        //right減回去, left加回去
        //string取sub string的用法
        return s.substr(left+1, (right - 1) - (left + 1) + 1);
    }
};
```

## 4.Performance

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LLISrl_1VRJ0HMig2lv%2F-LLJGK2i8h3b5Hoqii0y%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-09-01%20%E4%B8%8B%E5%8D%884.34.37.png?alt=media\&token=a90bd8da-250b-4b80-8740-f524b46b1002)