Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd"
Output: "bb"
Solution:
Insert ‘ ‘ in between every element of string to simplify odd and even case. Then iterate through string and find the maximum length if current char is pivot.
class Solution {
public:
string longestPalindrome(string s) {
vector<char> t{' '};
for(char c:s){
t.push_back(c);
t.push_back(' ');
}
int len = -1;
int pos = -1;
for(int i=0;i<t.size();i++){
int l = i, r = i;
while(l>=0&&r<t.size()&&t[l]==t[r]){
l--;
r++;
}
if(r-l+1>len){
len = r-l-1;
pos = l+1;
}
}
vector<char> ans;
for(int i=pos;i<pos+len;i++){
if(t[i]==' ')continue;
ans.push_back(t[i]);
}
return string(ans.begin(),ans.end());
}
};