가장 긴 팰린드롬

가장 긴 팰린드롬

앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다.

문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요.

예를들면, 문자열 s가 abcdcba이면 7을 return하고 abacde이면 3을 return합니다.

제한사항

문자열 s의 길이 : 2,500 이하의 자연수

문자열 s는 알파벳 소문자로만 구성

입출력 예

s: “abcdcba”

answer: 7

s: “abacde”

answer: 3

문제 해결 방안

입력받은 문자열을 부분 문자열로 나누고 그 부분문자열들의 크기를 2개부터 시작해서 본래 크기와 같은 크기가 될때까지 앞뒤가 같은 문자인지를 확인하는 작업을 합니다.

이때 효율성 테스트를 통과하기 위해 문자열을 나누는 함수를 한번만 사용하고 확인하는 함수에서는 미리 잘라놓은 문자열을 이용하여 검사합니다.

가장 긴 팰린드롬의 길이를 구하는 것이기 때문에 본래 크기의 문자열부터 시작하여 2개 크기의 문자열을 검사하는 역순으로 수행합니다.

class Solution
{
    public int solution(String s)
    {
        int answer = 0;
        char[] chars = s.toCharArray();

        for(int size = chars.length - 1; size > 1; --size){
            for(int padding = 0; padding < chars.length - size; padding++){
                if(isPalindrome(chars, padding, padding + size)){
                    if(answer < size)
                        return size + 1;
                }
            }
        }

        if(answer == 0)
            return 1;
        return answer + 1;
    }

    public boolean isPalindrome(char[] chars, int startIndex, int endIndex){
        int size = endIndex - startIndex + 1;

        for(int i = 0; i < size; i++){
            if(chars[startIndex + i] != chars[startIndex + size-1 - i] ){
                return false;
            }
        }
        return true;
    }
}