99클럽 코테 스터디 30일차 TIL - 문자열 (LeetCode 5번)

항해99 코테 스터디 30일차 문제인 리트코드의 5번은 문자열에서 가장 긴 팰린드롬을 찾는 문제다. 난이도는 Medium이며 문자열 탐색을 통해 해결할 수 있다.

 

오늘의 문제 - XXX 문제 정보

문제 키워드

- 문자열

난이도

- Medium

 

문제 요약

• 영어와 숫자로만 이루어진 길이 1000 이하의 문자열 s가 주어진다.
• s의 substring 중 가장 긴 팰린드롬을 구하여라.

 

문제 풀이 과정  

• 팰린드롬은 항상 홀수인 경우와 짝수인 경우의 계산이 달라 복잡하다. 따라서 두 경우를 나누어서 구하면 된다.
• 기준점을 잡고 좌우로 한칸씩 늘려가면서 팰린드롬인지 확인한다. 이에 따라 가장 긴 팰린드롬의 길이와 위치를 갱신한다.

코드

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        int startIdx = 0, longest = 1;
 
        for(int mid = 1; mid < n; mid++) {
            // 1. 홀수 팰린드롬
            int oddMax = 0;
            for(int dist = 1; mid-dist >= 0 && mid+dist < n; dist++) {
                if (s.charAt(mid-dist) != s.charAt(mid+dist)) {
                    break;
                }
                oddMax++;
            }
 
            if (oddMax*2+1 > longest) {
                startIdx = mid-oddMax;
                longest = oddMax*2 + 1;
            }
 
            // 2. 짝수 팰린드롬
            int evenMax = 0;
            for(int dist = 1; mid-dist >= 0 && mid+dist <= n; dist++) {
                if (s.charAt(mid-dist) != s.charAt(mid+dist-1)) {
                    break;
                }
                evenMax++;
            }
 
            if (evenMax*2 > longest) {
                startIdx = mid-evenMax;
                longest = evenMax*2;
            }
        }
 
        return s.substring(startIdx, startIdx + longest);
    }
}

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