# Leecode05. Longest palindrome substring -- leecode100 question series

## I'm Xiao Zhang , Determined to use the most concise code to do the most efficient expression

The following is my personal solution , Each problem includes all solutions as much as possible , And achieve the optimal solution , Welcome to collect ！ Leaving a message. ！

Leecode01. Sum of two numbers （C++） hash
Leecode03. Longest substring without repeating characters （C++） hash + The sliding window

### Problem description

Give you a string s, find s The longest palindrome substring in .

Example 1：
Output ：“bab”
explain ：“aba” It's the same answer .

Example 2：
Input ：s = “cbbd”
Output ：“bb”

Example 3：

Input ：s = “a”
Output ：“a”

Example 4：
Input ：s = “ac”
Output ：“a”

Tips ：
1 <= s.length <= 1000
s Just numbers and letters （ Capital and / Or lowercase ） form

### Ideas

Center detection method （ Common methods for solving palindrome strings ）

### Complexity analysis

Time complexity O ( n 2 ) O(n^2) , among n n Is the length of the string . The length is 1 1 and 2 2 The palindrome centers are n n and n − 1 n-1 individual , Each palindrome center will expand outward at most O ( n ) O(n) Time .

Spatial complexity O ( 1 ) O(1) .

### Code 1 （ Universal code ）

class Solution {

public:
string longestPalindrome(string s) {

int left = 0, right = s.length() - 1;
int maxLen = 0, nowLen = 0;
string res = "";
for(int i = 0; i < s.length(); i++) {

// Palindrome sequence is odd
nowLen = 1;
int l = i-1, r = i+1;
while (l >= left && r <= right) {

if(s[l] == s[r]) {

nowLen += 2;
} else {

break;
}
l--; r++;
}
if(nowLen > maxLen) {

maxLen = nowLen;
res = s.substr(l+1, maxLen);
}
// Palindrome sequence is even
nowLen = 0;
l = i, r = i+1;
while (l >= left && r <= right) {

if(s[l] == s[r]) {

nowLen += 2;
} else {

break;
}
l--; r++;
}
if(nowLen > maxLen) {

maxLen = nowLen;
res = s.substr(l+1, maxLen);
}
}
return res;
}
};


### Code 2： Function reuse

class Solution {

public:
int func(int& nowLen, int l, int r, string s) {

while (l >= 0 && r <= s.length()) {

if(s[l] == s[r]) {

nowLen += 2;
} else {

break;
}
l--; r++;
}
return l;
}
string longestPalindrome(string s) {

int maxLen = 0, nowLen, sta;
string res = "";
for(int i = 0; i < s.length(); i++) {

// Palindrome sequence is odd
nowLen = 1;
sta = func(nowLen, i-1, i+1, s);
if(nowLen > maxLen) {

maxLen = nowLen;
res = s.substr(sta+1, maxLen);
}
// Palindrome sequence is even
nowLen = 0;
sta = func(nowLen, i, i+1, s);
if(nowLen > maxLen) {

maxLen = nowLen;
res = s.substr(sta+1, maxLen);
}
}
return res;
}
};