[LeetCode] 5. Longest Palindromic Substring

https://leetcode.com/problems/longest-palindromic-substring/

Longest Palindromic Substring - LeetCode

leetcode - Longest Palindromic Substring

문제 유형 : 문자열 처리, 투포인터

문제 난이도 : Medium

 

문제

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

 

문자열 s가 주어집니다. s의 가장 긴 팰린드롬 부분 문자열을 반환하시오.

 

풀이

문자열의 각 문자별로 팰린드롬 부분 문자열의 중심으로 잡고, 각 자리에서 구할 수 있는 최대의 팰린드롬 문자열 길이를 구합니다.

그리고, 매번 최대의 길이를 만드는 시작 부분과 문자열 길이를 업데이트합니다.

순회가 끝나면, 시작 부분과 길이로 부분 문자열을 만들어서 반환하도록 합니다.

 

코드

C++

class Solution {
public:
    int expandAroundCenter(const string& s, int left, int right) {
        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            left--;
            right++;
        }
        return right - left - 1;
    }

    string longestPalindrome(string s) {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);

        const int n = s.size();
        int maxLen = 0;
        int start = 0;

        for (int i = 0; i < n; i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = max(len1, len2);

            if (len > maxLen) {
                maxLen = len;
                start = i - (len - 1) / 2;
            }
        }

        return s.substr(start, maxLen);
    }
};