Leetcdoe: Longest Palindromic Substring

Difficulty: Medium

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Subscribe to see which companies asked this question

Hide Tags

 String

Show Similar Problems

-----------------------------------------------------------------------------------

Scan the string from left to right with the center of potential palindrome. There are two cases in this method:

case 1:

abba

case 2:

aba

Check the two cases in each scan. 

//////////////////////////////////////////

//codes

class Solution {

 public:

        string longestPalindrome(string s) {

               //check input

               if (s.size()<2)return s;

               string fnl;

               int i = 1;

               while (i<s.size()){

                      //case 1

                      int l = i, r = i;

                      while (l > -1 && r<s.size()){

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

                                   l--;

                                   r++;

                                   continue;

                            }

                            else break;

                      }

                      ++l;

                      --r;

                      string tmp;

                      tmp.assign(s, l, r - l + 1);

                      fnl = tmp.size()>fnl.size() ? tmp : fnl;

                      

                      //case 2

                      l = i - 1, r = i;

                      while (l > -1 && r<s.size()){

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

                                   l--;

                                   r++;

                                   continue;

                            }

                            else break;

                      }

                      ++l;

                      --r;

                      string tmp1;

                      tmp1.assign(s, l, r - l + 1);

                      fnl = tmp1.size()>fnl.size() ? tmp1 : fnl;

                      

                      //check left length

                      if (s.size() - i + 1<fnl.size() / 2)break;

                      i++;

               }

               return fnl;

        }

 };