Dry run:
Since we need substrings, lets select index i and expand to right and left and check if expanded substrings form palindromes.
There can be odd and even sized palindromes.
So lets start left=i, right i for odd sized palindromes
left=i, right=i+1 to look for even sized palindromes
by keeping track of maxlen and start index.
Lets start with i=2
Below is example of odd palindrome
b a d a m maxlen=1
lr
b a d a m maxlen=r-l+1=3-1+1=1
l r
Let's take another example:
baaaa
Let's start at index 2
b a a a a maxlen=2
l r
b a a a a maxlen=4
l r
string longestPalindromicSubstring(string &s) {
int n=s.length();
int maxlen=0;
int start=0;
for(int i=0;i<n;i++){
int l=i;
int r=i;
while(l>=0 && r<n && s[l]==s[r]){
if(maxlen<r-l+1){
maxlen=r-l+1;
start=l;
}
l--;
r++;
}
l=i;
r=i+1;
while(l>=0 && r<n && s[l]==s[r]){
if(maxlen<r-l+1){
maxlen=r-l+1;
start=l;
}
l--;
r++;
}
}
return s.substr(start,maxlen);
}