[string] longest palindromic substring

✅ Problem

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

 

✅ Approach & Solution

방식)

• 투 포인터 방식을 사용한다.
  • offset, limit 사용 (아래 코드에서 left가 offset, maxLen이 limit이 됨)
• 팰린드롬이 될 수 있는 최소 길이(1 초과)의 값을 기준으로 양 옆으로 확장해나간다.
  • 최소 길이 : 2 or 3
  • ex) aa, aba

class Solution {
    
    int left, maxLen;

    public String longestPalindrome(String s) {
        // 문자 길이 저장
        int len = s.length();

        // 길이가 1인 경우 예외 처리
        if (len < 2) return s;

        // 우측으로 한 칸씩 이동하며 투 포인터 조사
        for (int i = 0; i < len - 1; i++) {
            extendPalindrome(s, i, i + 1); // 2칸짜리 투 포인터
            extendPalindrome(s, i, i + 2); // 3칸짜리 투 포인터
        }

        // 왼쪽과 최대 길이만큼을 더한 오른쪽만큼의 문자를 정답으로 리턴
        return s.substring(left, left + maxLen);
    }

    public void extendPalindrome(String s, int start, int end) {
        // 투 포인터가 유효한 범위 내에 있고 양쪽 끝 문자가 일치하는 팰린드롬인 경우 범위 확장
        while (start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) {
            start--;
            end++;
        }

        // 기존 최대 길이보다 큰 경우 값 교체
        if (maxLen < end - start - 1) {
            left = start + 1;
            maxLen = end - start - 1;
        }
    }
}

 

시간 복잡도

• O(n^2)
  • extendPalindrome 메서드는 최대 O(n)이고, longestPalindrome 메서드에서 최대 2 * (n-1)번 호출됨