# 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)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jenhsuan.gitbook.io/algorithm/leetcode/5.-longest-palindromic-substring.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.