(Leet Code c++)Longest Palindromic Substring

5. Longest Palindromic Substring

 

Given a string s, return the longest palindromic substring in s.

 

Example 1:

Input: s = "babad" Output: "bab" Note: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd" Output: "bb"

Example 3:

Input: s = "a" Output: "a"

Example 4:

Input: s = "ac" Output: "a"

 

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters (lower-case and/or upper-case),

 

주어진 s에서 가장 긴 팰린드롬을 찾아야 한다.

흔히 팰린드롬을 구하는 방법이다.

가운데에서 left, right를 비교해 나가는 방식이다.

class Solution {
public:
    string longestPalindrome(string s) {
        int size = s.size(), start = 0, end = 0;
        
        if(size == 0){
            return "";
        }
        
        for(int mid = 0; mid < s.size(); mid++){
            int l1 = getLength(mid, mid, s);
            int l2 = getLength(mid, mid + 1, s);
            
            if(l1 > end - start){
                start = mid - l1 / 2;
                end = mid + l1 / 2;
            }
            
            if(l2 > end - start){
                start = mid + 1 - l2 / 2;
                end = mid + l2 / 2;
            }
        }
        
        return s.substr(start, end - start + 1);
    }
    
    int getLength(int left, int right, string s){
        int len = 0;
        
        while(left >= 0 && right < s.size()){
            if(s[left] == s[right]){
                len = right - left + 1;
                left--;
                right++;
            }
            else{
                break;
            }
        }
        
        return len;
    }
};