<p>Given a string <code>s</code>, return <em>the longest</em> <span data-keyword="palindromic-string"><em>palindromic</em></span> <span data-keyword="substring-nonempty"><em>substring</em></span> in <code>s</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;babad&quot;
<strong>Output:</strong> &quot;bab&quot;
<strong>Explanation:</strong> &quot;aba&quot; is also a valid answer.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;cbbd&quot;
<strong>Output:</strong> &quot;bb&quot;
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 1000</code></li>
	<li><code>s</code> consist of only digits and English letters.</li>
</ul>

class Solution {
public:
bool isPalin(string s)
{
    bool palin=true;
    int left=0;
    int right = s.size()-1;
    while(left<right)
    {
        if(s[left]!=s[right]){palin=false; break;}
        left++;right--;
    }
    return palin;
}
 string longestPalindrome(string s)
{
    int left=0;
    int right=1;
    string res="";
    string finalstr ="";
    string maxsizestr =s.substr(0,1) ;
    int size =0;
    int maxsize =0;
    bool threechar=false;
    if(s.size()<=1){return s;}
    // if(s.size()==2){
    //     if(isPalin(s)){return s;}
    //     else return s.substr(0,1);        
    // }
    while(left>=0 && right<s.size())
    {
        //ba
        res=s.substr(left,(right-left+1));//e

        if(!isPalin(res))
        {
            if(!threechar)
            {
                right++;
                threechar=true;
            }
            else
            {
                left++;
                threechar=false;
            }
        }
        else
        {       
            //palin
            cout<<"YES"<<endl;
            //give left right, find longest,,after that, left right as it is
            int start = left;
            int end=right;
            cout<<"res = "<<res<<" left = "<<left<<", right = "<<right<<", maxszie = "<<maxsize<<endl;
            while(start>=0 && end< s.size())
            {               
                if(!isPalin(s.substr(start,(end-start+1))))
                {                    
                    break;
                } 

                size = end-start+1; 
                finalstr = s.substr(start,size);        
                start--;end++;
            }
             if(maxsize<=size)
            {
                cout<<"maxsize = "<<maxsize<<" maxsizestr = "<<maxsizestr<<endl;
                maxsize = size;
                maxsizestr=finalstr;
            }

            right++;    
           
        }
       
        cout<<"maxsize = "<<maxsize<<" left = "<<left<<", right = "<<right<<", maxszie = "<<maxsize<<endl;
    }
    return maxsizestr;

}
































// bool ispalin(string s)
// {
//     int start=0;
//     int end=s.size()-1;
//     //cout<<"s = "<<s<<endl;
//     while(start<end)
//     {
//         if(s[start]!=s[end]){return false;}
//         start++;end--;
//     }
//     return true;
// }


//  string longestPalindrome(string s)
//  {
//     int size = s.size();
//     int index=0;
//     int max=0;
//     string res;
//     string maxString = s.substr(0,1);;
//     if(size<=1){return s;}
//    while(index<size)
//    {
//         //even cabbak
//         int left=index;
//         int right=index+1;
//         if(left>=0 && right<size && s[left]==s[right])
//         {               
//             while(left>=0 && right<size && ispalin(s.substr(left,right-left+1)))
//             {
//                     left--;right++;
//             }
//                 left++;right--;
//                 res = s.substr(left,right-left+1);
//             if(res.size()>max)
//             {
//                 max = res.size();
//                 maxString=res;
//             }   
//         }

//         //odd cbdba
//         if(index>0)
//         {
//             left=index-1;
//             right=index+1;
//             if(left>=0 && right<size && s[left]==s[right])
//             {               
//                 while(left>=0 && right<size && ispalin(s.substr(left,right-left+1)))
//                 {
//                      left--;right++;
//                 }
//                  left++;right--;
//                  res = s.substr(left,right-left+1);
//                 if(res.size()>max)
//                 {
//                     max = res.size();
//                     maxString=res;
//                 }   
//             }
//         }
    
//     index++;
//    }

//    return maxString;









//     // //go each and expand
//     // int mid=0;
//     // int left=0;
//     // int right=0;
//     // int max=0;
//     // char prev;   
//     // string repeat; 
//     // string res =s.substr(0,1);
//     // if(s.size()<=1){return s;}


//     //    while(mid<s.size())
//     //    {
//     //         left=mid;
//     //         right=mid;
//     //         repeat.clear();
//     //         while(left>=0 && right<s.size()&& s[left]==s[right])
//     //         {
//     //             left--;right++;                
//     //         }
//     //         left++;right--;
//     //         cout<<", left = "<<left<<", right = "<<right<<endl;
//     //         cout<<", right-left+1 = "<<right-left+1<<endl;
//     //         if(right-left+1>1)
//     //         {                
//     //             string snew=s.substr(left,right-left+1);
//     //             if( ispalin(snew))
//     //             {
//     //                 if(max<snew.size())
//     //                 {
//     //                     max=snew.size();                        
//     //                     res=snew;
//     //                 }
//     //             }
//     //         }
//     //         prev=s[mid];
//     //         repeat.push_back(prev);
//     //         mid++;
//     //         while(s[mid]==prev)
//     //         {
//     //             prev=s[mid];
//     //             mid++;        
//     //             repeat.push_back(prev);
//     //             if(max<repeat.size()){max=res.size(); res=repeat;}        
//     //         }
//     //    }

        
    

//   //  return res;
//  }












// bool IsPalindrome(string s)
// {
//     int left=0; int right=s.size()-1;
//     while(left<right)
//     {
//         if(s[left]!=s[right]){return false;}
//         left++; right--;
//     }
//     return true;
// }


//  string longestPalindrome(string s)
//  {
//     //  yuabcbamnabhsdffds
//     //abcdafgpgfadcba
//     //p start-1 & start+1
    
//     //abcdafggfadcba
//     //g start start+1 ,  start-1, start+2


//     int start=0;
//     int maxsize=0;
//     int left=0;
//     int right = 0;
//     string maxstring ="";
//     if(s.size()>1)
//     { 
//         maxstring = s.substr(0,1);       
//         while(start<=s.size()-1)
//         {
//             left=start-1;
//             right = start+1;
//             while(left>=0 && right<=s.size()-1)
//             {
//                 string test=s.substr(left,right-left+1);
//                 if(IsPalindrome(test))
//                 {
//                     if(maxsize<=test.size()){maxsize=test.size();maxstring=test;}
//                     //cout<<"left = "<<left<<" , test = "<<test<<endl;
//                 }
//                 left--, right++;
//                 //cout<<"1condition = "<<endl;
//             }

//             left=start;
//             right = start+1;
//             while(left>=0 && right<=s.size()-1)
//             {
//                 string test=s.substr(left,right-left+1);
//                 if(IsPalindrome(test))
//                 {
//                     if(maxsize<=test.size()){maxsize=test.size();maxstring=test;}
//                     //cout<<"2left = "<<left<<" , test = "<<test<<"maxstring = "<<maxstring<<endl;
//                 }
//                 left--, right++;
//                  //cout<<"2condition = "<<endl;
                
//             }
//             //cout<<"start = "<<start<<", maxstring = "<<maxstring<<endl;
//             start++;
            

//         }
//         return maxstring;
//     }
//     else if(s.size()>=1 )
//     {
//         maxstring =s;
//     }    
//     return maxstring;
    







//     // //  find next letter same
//     // // find next of that until end
//     // //  check start end is palin
//     //     vector<string> vecstr;
//     //    int start=0;
//     //    int nextLetterPos=0;
//     //    int maxsize=0;
//     //    string maxstring;
//     //    string out;
//     //    if(s.size()>1)
//     //    {
//     //         while(start<=s.size()-1)
//     //         {
//     //             while(nextLetterPos!=string::npos)
//     //             {
//     //                 int pos =  s.find(s[start], nextLetterPos+1);
//     //                 //cout<<"pos = "<<pos<<", start = "<<start<<endl;
//     //                 nextLetterPos = pos;
//     //                 if(pos!=string::npos)
//     //                 {                        
//     //                     out = s.substr(start,pos-start+1);
//     //                     if(IsPalindrome(out))     
//     //                     {
//     //                         //cout<<" str = "<<out<<endl;                               
//     //                         if(maxsize<out.size()){ maxsize = out.size(); maxstring = out;}

//     //                     }

//     //                 }
//     //             }
//     //         start++;
//     //         nextLetterPos=start;                                  
//     //         }
//     //         if(maxsize==0){maxstring = s[0];}
//     //    }
//     //    else { return s;}
//     // string res="";

//     // return maxstring;




//     //  //substr
//     // //  outside
//     // //  right in, 
//     // //  not same
//     // //  left in, 
//     // //  not same
//     // //  when same, both left right move and check, if not same, update indexlongest
//     // //  right in
//     // int indexstart=0;int maxindexstart=0;
//     // int indexend=0;int maxindexend=0;
//     // int left=0;
//     // bool switchflag=true;
//     // int right=s.size()-1;
//     // int maxs=0;
//     // while(left<right)
//     // {
//     //     if(s[left]==s[right])
//     //     {
//     //         indexstart=left; indexend=right;
//     //         left++; right--;
//     //     }
//     //     else
//     //     {
//     //         int nextright=right-1;
//     //         int nextleft=left+1;
//     //         if(s[left]==s[nextright]){right--;}
//     //         else if(s[nextleft]==s[right]){left++;}
//     //         else if(switchflag){right--;switchflag=false;}
//     //         else {left++; switchflag=true;}
//     //     }
//     //     cout<<"left = "<<left<<", s[left]= "<<s[left]<<", right ="<<right<<"s[right]="<<s[right]<<endl;
//     //     if(maxs<(indexend-indexstart)){maxs = indexend-indexstart;maxindexstart =indexstart;maxindexend= indexend;}
//     //     cout<<"indexstart = "<<indexstart<<",indexend= "<<indexend<<", maxindexstart ="<<maxindexstart<<"maxindexend="<<maxindexend<<endl;
//     // }
//     // string res = s.substr(maxindexstart, maxindexend-maxindexstart+1);
//     // return res;
     
//  }


// bool IsPalindrome(string s)
// {
//     int left=0; int right=s.size()-1;
//     while(left<right)
//     {
//         if(s[left]!=s[right]){return false;}
//         left++; right--;
//     }
//     return true;
// }


























    // string longestPalindrome(string s) {
    //     //find if string palindromic
    //     //abcdefedchybjar
    //     // i i+1 are same --check
    //     // i-1 i+1 same--check
    //     //size- map- size string
    //     int left=0;
    //     int temp=0;
    //     int right=0;
    //     int palindsize=0;
    //     int maxpalindrome=0;
    //     map<int, string> palinMap;
    //     int size = s.size();
    //     for (int i=0; i<size-1;i++)        
    //     {
    //         if(s[i]==s[i+1])
    //         {
    //             left=i;
    //             right =i+1;
    //         }
    //          else if(i>0 && s[i-1]==s[i+1])
    //         {
    //             //go left and right and check if they equal
    //             left=i-1;
    //             right =i+1;
    //         }
            
    //         while(s[left]==s[right])
    //         {
    //             palindsize = right-left+1;
    //             // if(left>0) {palindsize = right-left+1;}
    //             // else {palindsize = right-left+2;}
    //             temp=left;

    //             if(left==0 || right == size-1){ break;}  
    //             left--; right++;              
    //         }
    //         palinMap[palindsize] = s.substr(temp, palindsize);

    //          cout<<"i ="<<i<<", left, right, = "<<left<<", "<<right<<", palindsize = "<<palindsize
    //          <<",  s.substr(left, palindsize) = "<< s.substr(left+1, palindsize)<<endl;
    //         left=0;
    //         right=0;
    //         palindsize=0;
    //     }
    //     if(!palinMap.empty())
    //     return (palinMap.rbegin())->second;
    //     else
    //     return s;
        
    //     // for (int i=1; i<s.size()-2;i++)        
    //     // {
    //     //     if(s[i]==s[i+1])
    //     //     {
    //     //         //go left and right and check if they equal
    //     //         left=i;
    //     //         right =i+1;
    //     //     }
    //     //     else if(s[i-1]==s[i+1])
    //     //     {
    //     //         //go left and right and check if they equal
    //     //         left=i-1;
    //     //         right =i+1;
    //     //     }
    //     //     else
    //     //     {
    //     //     left=0;
    //     //     right=0;
    //     //     palindsize=0;
    //     //         continue;
    //     //     }
    //     //     while(left>=0 && right<=s.size()-1 && s[left]==s[right])
    //     //     {
    //     //         palindsize = right-left;
    //     //         if(left!=0 &&  right!=s.size()-1)
    //     //         {left--;
    //     //         right++;}
    //     //     }
    //     //     palinMap[palindsize] = s.substr(left, palindsize);
    //     //     cout<<"i ="<<i<<", left, right, = "<<left<<", "<<right<<", palindsize = "<<palindsize<<endl;//", s[i]==s[i+1] = "<<s.substr(left, palindsize)<<endl;     
    //     //     left=0;
    //     //     right=0;
    //     //     palindsize=0;
    //     // }
        
    //     //int maxsize = (palinMap.rbegin())->second;
    //     //return (palinMap.rbegin())->second;
    //     return s;
    // }
};
240780