[PS] Leet | 5. 가장 긴 팰린드롬 하위문자열

문제

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

예시

Example 1:
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

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

조건

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

답

문자열을 순회하면서 각 인덱스마다 양옆으로 하위 문자열을 확장하면서 팰린드롬인지 판단합니다.

 

문자열 길이가 짝수일 때와 홀수일 때 두 가지 모양의 팰린드롬이 존재하므로,

 

각 인덱스마다 인덱스 번호 [i]를 중심으로 하는 경우와 [i, i+1]를 중심으로 하는 경우 두가지의 팰린드롬을 모두 탐색합니다.

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let left = 0, right = 0;
    let maxPal = '';
    let pal = '';

    for (let i=0; i<s.length; ++i) {
        left = i;
        right = i;

        while (left >= 0 && right < s.length && s[left] === s[right]) {
            left--;
            right++;
        }
        pal = s.slice(left+1, right);
        maxPal = (maxPal.length < pal.length)? pal : maxPal;

        left = i;
        right = i+1;

        while (left >= 0 && right < s.length && s[left] === s[right]) {
            left--;
            right++;
        }
        pal = s.slice(left+1, right);
        maxPal = (maxPal.length < pal.length)? pal : maxPal;
    }

    return maxPal
};

시간 복잡도 : O(n^2)

공간 복잡도 : O(1)