[JS] Longest Palindromic Substring

🔒 문제 (LeetCode 5)

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

Constraints:

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

 

🌊 입출력

Example 1:

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

Example 2:

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

 

---

 

🔑 해결

🌌 알고리즘

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let ll = 0  // 가장 긴 팰린드롬의 left
    let rr = 0  // 가장 긴 팰린드롬의 right
    
    for(let i = 0; i < s.length; i++) {
        // 팰린드롬의 중간에서 시작하여 substring 길이를 늘려가며 팰린드롬 여부 확인
        // 길이가 홀수 일 때 중간점은 j=i, 짝수일 때는 j=i+1
        for(let j of [i, i+1]) {
            for(let l = i, r = j; s[l] && s[l] === s[r]; l--, r++) {
                // l, r으로 새로 찾은 팰린드롬이 더 긴 경우 ll, rr 업데이트
                [ll, rr] = r - l + 1 > rr - ll + 1 ? [l, r] : [ll, rr]
            }
        }
    }
    
    return s.slice(ll, rr + 1)
};