[LeetCode] 5. Longest Palindromic Substring 풀이 및 설명 (Java)

✔️ 오늘의 리트코드 공부 기록 – Longest Palindromic Substring (생각보다 사고 전환이 핵심이었다)

---

 

문제 요약 (Longest Palindromic Substring)

문자열에서 가장 긴 팰린드롬(앞뒤가 동일한 연속 부분 문자열)을 찾는 문제

 

문제링크: https://leetcode.com/problems/longest-palindromic-substring

 

 

처음엔 가장 자연스럽게 이런 생각이 들었다.

• “왼쪽부터 substring 을 늘려가면서 확인하면 되지 않을까?”
• “아니면 길이를 1, 2, 3... 이렇게 늘리면서 가장 긴 팰린드롬을 찾을까?”

그런데 조금만 생각해보니 이 방식은 결국 모든 substring 을 확인해야 한다.

팰린드롬 확인(O(n)) + substring 개수(O(n²)) = 사실상 O(n³).

DP를 쓰면 O(n²)까지 줄일 수는 있지만, 뭔가 더 좋은 접근이 있을 것 같았다.

---

😮 여기서 관점을 바꾸어야 한다.

팰린드롬의 조건은 결국 하나다. 👉 “좌우가 대칭일 것”

그래서 질문을 이렇게 바꾼다. 👉 “팰린드롬은 어디서 정의될까?”

정답은  “중심(center)”

팰린드롬은 항상 어떤 중심을 기준으로 좌우가 동일하게 퍼져나가는 구조다.

그렇다면 substring 을 전부 확인할 필요가 없다. 👉 “모든 중심을 기준으로 좌우로 확장하면 되지 않을까?”

 

---

💡 핵심 아이디어

 

그리고 이 접근이 바로 Expand Around Center 방식이다.

• 중심 후보는 최대 2N 
  • 문자 기반 중심 (i, i)
  • 문자 사이 중심 (i, i+1)
• 각 중심에서 좌우로 확장하며 가장 긴 팰린드롬을 찾는다
• 팰린드롬이 깨지는 순간 종료 → 불필요한 탐색 없음

결과적으로

• Time: O(n²)
• Space: O(1)

---

 

코드 (Java)

문자열의 모든 인덱스를 ‘중심(center)’으로 보고 좌우로 확장하며 가장 긴 팰린드롬을 찾는다.

class Solution {

  public String longestPalindrome(String s) {
    int len = s.length();
    int maxLength = 1;
    int start = 0;
    for (int i = 0; i < len; i++) {
      int oddLen = expand(s, i, i, len);
      int evenLen = Math.max(maxLength, expand(s, i, i + 1, len));

      int currentMax = Math.max(oddLen, evenLen);
      if (currentMax > maxLength) {
        maxLength = currentMax;
        start = i - (maxLength - 1) / 2;
      }
    }

    return s.substring(start, start + maxLength);
  }

  private static int expand(String s, int left, int right, int len) {
    while (left >= 0 && right < len) {
      if (s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
      } else {
        break;
      }
    }
    return right - left - 1;
  }
}

 

 

📈 Time / Space Complexity

• 시간: O(n²)  
• 공간:  O(1)

---

DP 접근 (대안)

 

DP 로도 풀 수 있다.

dp[i][j] = true → s[i..j] 가 팰린드롬
조건: s[i] == s[j] && (j - i < 2 || dp[i+1][j-1]) 

 

 

하지만,

• n² 테이블 전체를 채워야 함
• 메모리 접근 비용 큼
• 실제 실행 시간은 보통 더 느림

그래도 한 번쯤 구현해볼 가치는 있다.

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        if (n < 2) return s;

        boolean[][] dp = new boolean[n][n];
        int start = 0, maxLen = 1;

        for (int i = 0; i < n; i++) dp[i][i] = true;

        for (int j = 1; j < n; j++) {
            for (int i = 0; i < j; i++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (j - i < 3) dp[i][j] = true;
                    else dp[i][j] = dp[i + 1][j - 1];
                }

                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    start = i;
                }
            }
        }

        return s.substring(start, start + maxLen);
    }
}

 

---

 

📝 이번 문제에서 얻은 깨달음

• 문제 구조가 주는 패턴 / 대칭성 / 중심 개념을 적극 활용하자
• odd 팰린드롬만 보면 abba 같은 even 팰린드롬을 놓친다 → (i, i) + (i, i+1) 둘 다! (처음 odd 만 처리함)
• while 종료 시 left/right 는 한 칸 더 나가 있으니 right - left - 1 로 계산해야 함 (처음 right - left +1 로 함)
• 최종 substring 은 s.substring(start, start + maxLen) 으로 하기 위해 start = i - (cur - 1) / 2 을 사용할 수 있다.
  • 팰린드롬은 중심 기준으로 좌우 대칭 왼쪽으로 뻗은 길이가 (cur - 1) / 2 이다!
• DP도 가능하지만, 실제 성능은 불필요한 확장을 빨리 멈추는 center expansion 이 더 좋다.

 

 

Longest Palindromic Substring 은

“모든 substring 을 검사하는 문제”가 아니라
“팰린드롬이 만들어지는 구조를 이해하는 문제”