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

문제설명

앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다.
문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요.

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

제한사항

• 문자열 s의 길이 : 2,500 이하의 자연수
• 문자열 s는 알파벳 소문자로만 구성

해결 방법

팰린드롬이 되는 문자열은 길이가 홀수, 짝수 두 가지 경우로 나눌 수 있다.

 

따라서, 각 문자에서 홀수, 짝수가 되는 두가지 경우의 팰린드롬을 탐색한다.

 

JAVA

package programmers;

import java.util.*;

public class p_12904 {
	public static int solution(String s) {
		int max = 1;
		for(int i = 1; i < s.length() - 1; i++) {
			int left = i - 1;
			int right = i + 1;
			int cnt = 0;
			
			while(left >= 0 && right < s.length()) {
				if(s.charAt(left) == s.charAt(right)) {
					left--;
					right++;
					cnt++;
				}
				else break;
			}
			max = Math.max(1 + 2 * cnt, max);
		 
			if(s.charAt(i) == s.charAt(i + 1)) {
				left = i;
				right = i + 1;
				cnt = 0;
				while(left >= 0 && right < s.length()) {
					if(s.charAt(left) == s.charAt(right)) {
						left--;
						
						
						right++;
						cnt++;
					}
					else break;
				}
				max = Math.max(2 * cnt, max);
			}
		}
		return max;
	}
	public static void main(String[] args) {
		String s1 = "abcdcba";
		String s2 = "abacde";
		
		System.out.println(solution(s1));
	}
}