Problem description:

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:
Input: “babad”
Output: “bab”

Note: “aba” is also a valid answer.

Example:
Input: “cbbd”
Output: “bb”
https://goo.gl/5cmsJy

Solution:

The basic idea is to use an iterative function to check whether if the left and right character is the same as each others. One thing to notice is that, the center might be in the middle of two character, for example:

1
2
aabbc, length 5, mid is index[3]
aabb, length 4, mid is in the middle of index[1] index [2]

Therefore, we need to check whether if the center is a character or not. We can use a subfunction to help us check. By using two pointer, left and right, we can use two different input:

  1. left == right:
    expand from 1 character
    1
    2
    3
    a a b c d
        |
       r l
  1. left != right:
    expand from 2 characters
    1
    2
    3
    a b c d
      | | 
      l r

  • first time 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    class Solution {
    public:
        string expandAroundCenter(string s, int c1, int c2) {
          int l = c1, r = c2;
          int n = s.length();
          while (l >= 0 && r <= n-1 && s[l] == s[r]) {
            l--;
            r++;
          }
          return s.substr(l+1, r-l-1);
    }
     
    string longestPalindrome(string s) {
          int n = s.length();
          if (n == 0) return "";
          string longest = s.substr(0, 1);  // a single char itself is a palindrome
          for (int i = 0; i < n-1; i++) {
            string p1 = expandAroundCenter(s, i, i);
            if (p1.length() > longest.length())
              longest = p1;

            string p2 = expandAroundCenter(s, i, i+1);
            if (p2.length() > longest.length())
              longest = p2;
          }
          return longest;
    }
    };

  • second time:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    class Solution {
    public:
        string longestPalindrome(string s) {
            string res;
            for(int i= 0; i< s.length(); i++){
                string tmp1= expand(s, i, i);
                string tmp2= expand(s, i, i+1);
                res= res.length()> tmp1.length() ? res: tmp1;
                res= res.length()> tmp2.length() ? res: tmp2;
            }
            
            return res;
        }
        
        string expand(string s, int l, int r){
            int left= l, right= r;
            while(left>=0 && right<= s.length() && s[left]==s[right]){
                left--;
                right++;
            }
            
            return s.substr(left+1, right-left-1); //since the while loop break because (left-- and right++)
        }
    };