[프로그래머스] Lv3. 가장 긴 팰린드롬

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12904

풀이

class Solution
{
    public int solution(String s)
    {
        int answer = 1;
        int n = s.length();
        for(int i = 0; i < n; i++) {
            // 홀수
            answer = Math.max(answer, palindrome(s, i, i));
            // 짝수
            answer = Math.max(answer, palindrome(s, i, i + 1));
        }
        return answer;
    }
    
    private int palindrome(String s, int lt, int rt) {
        int n = s.length();
        int length = 0;
        
        while(lt >= 0 && rt < n) {
            if(s.charAt(lt) == s.charAt(rt)) {
                length = rt - lt + 1;
                lt--;
                rt++;
            } else {
                break;
            }
        }
        return length;
    }
}

• 완전 탐색으로 풀면 O(N^3)
• 투포인터로 퍼져나가는 식으로 풀면 O(N^2)으로 시간을 줄일 수 있음
  • 퍼져나갈 때, substring의 길이가 홀수인지, 짝수인지에 따라 달라짐
  • 짝수라면, 둘을 묶어서 먼저 계산하고 투포인터 적용