문제 바로가기

Python

expand iteration -> next

Time Complexity: O(n^2)
Space Complexity: O(n)

• Runtime: 932 ms, faster than 82.24% of Python3 online submissions for Longest Palindromic Substring.
• Memory Usage: 14.4 MB, less than 37.86% of Python3 online submissions for Longest Palindromic Substring.

import typing

class Solution:
    def __init__(self):
        self.front = 0
        self.maxPalLen = 0
        
    def longestPalindrome(self, s: str) -> str:
        if len(s) == 1:
            return s
        
        for rear in range(1, len(s)):
            front, palLen = self.expandAroundCenter(rear - 2, rear, s)
            self.updateMaxPalindrome(front, palLen)
            
            # check even Palindrome
            if s[rear - 1] == s[rear]:
                front, palLen = self.expandAroundCenter(rear - 2, rear+1, s)
                self.updateMaxPalindrome(front, palLen)
            
        return s[self.front:self.front + self.maxPalLen]
    
    def expandAroundCenter(self, idxL, idxR, s: str) -> typing.Tuple[int, int]:
        while idxL >= 0 and idxR < len(s):
            if s[idxL] != s[idxR]:
                break
            idxL -= 1
            idxR += 1
        
        return idxL, idxR - idxL - 1
    
    def updateMaxPalindrome(self, front, palLen) -> None:
        if self.maxPalLen < palLen:
            self.maxPalLen = palLen
            self.front = front + 1

expand + next at the same time

• Runtime: 60 ms, faster than 99.84% of Python3 online submissions for Longest Palindromic Substring.
• Memory Usage: 14.3 MB, less than 82.11% of Python3 online submissions for Longest Palindromic Substring.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        
        if len(s) <= 1 or s == s[::-1]:
            return s
        
        start, maxlen = 0, 1
        
        for end in range(1, len(s)):
            sub1 = s[end-maxlen-1:end+1]
            sub2 = s[end-maxlen: end+1]
            
            if end-maxlen-1>=0 and sub1 == sub1[::-1]:
                start, maxlen = end-maxlen-1, maxlen+2
            elif end-maxlen>=0 and sub2 == sub2[::-1]:
                start, maxlen = end-maxlen, maxlen+1
        
        return s[start:start+maxlen]

Javascript

expand iteration -> next

• Runtime: 100 ms, faster than 91.51% of JavaScript online submissions for Longest Palindromic Substring.
• Memory Usage: 39.9 MB, less than 91.80% of JavaScript online submissions for Longest Palindromic Substring.

/**
 * @param {string} s
 * @return {string}
 */
const expandAroundCenter = function(s, left, right) {
    const n = s.length;
    while (left >= 0 && right < n && s[left] === s[right]) {
        left--;
        right++;
    }
    left++;
    return { start: left, len: right - left };
}

const longestPalindrome = function(s) {
    let maxLen = 0;
    let start = 0;
    const n = s.length;

    if (n === 1) return s;
    
    const updateMaxPalindrome = function(newStart, len) {
        if (maxLen < len) {
            maxLen = len;
            start = newStart;
        }
    };
    
    for (let i = 1; i < n; i++) {
        const { start, len } = expandAroundCenter(s, i-1, i+1);  // odd
        updateMaxPalindrome(start, len);
        
        if (s[i-1] === s[i]) {
            const { start, len } = expandAroundCenter(s, i-2, i+1);  // even
            updateMaxPalindrome(start, len);    
        }
    }
    
    return s.substring(start, start + maxLen);
};

expand + next at the same time

• Runtime: 120 ms, faster than 66.13% of JavaScript online submissions for Longest Palindromic Substring.
• Memory Usage: 39.7 MB, less than 96.36% of JavaScript online submissions for Longest Palindromic Substring.

/**
 * @param {string} s
 * @return {string}
 */
const longestPalindrome = function(s) {
    const n = s.length;
    if (n === 1) return s;
    
    let maxLen = 1;
    let start = 0;
    
    for (let end = 1; end < n; end++) {
        let i = 0
        let newStart = end - maxLen - 1;
        // [end - maxLen - 1, end]
        if (newStart >= 0) {
            for (; i < maxLen + 2; i++) {
                if (s[newStart + i] !== s[end - i]) break;
            }
            if (i === maxLen + 2) {
                start = newStart;
                maxLen = maxLen + 2;
                continue;
            }
        }
        
        // [end - maxLen, end]
        newStart += 1;
        i = 0
        for (; i < maxLen + 1; i++) {
            if (s[newStart + i] !== s[end - i]) break;
        }
        if (i === maxLen + 1) {
            start = newStart;
            maxLen = maxLen + 1;
        }
    }
    return s.substring(start, start + maxLen);
};