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

문제

가장 긴 팰린드롬

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

 

 

풀이

설명

문자열 s의 부분문자열 중 가장 긴 팰린드롬의 길이를 구하는 문제입니다.

 

홀수 길이 팰린드롬  또는 짝수 길이 팰린드롬이 있을 수 있습니다.

팰린드롬은 특정 인덱스를 중심으로 해서 좌우로 퍼져나가며 구할 수 있습니다.

문자열을 순회하면서 각 인덱스에서 만들 수 있는 가장 긴 팰린드롬의 길이를 구해 최대 길이를 비교합니다.

 

예시 코드

function solution(s) {
  let maxLength = 1;

  for (let i = 0; i < s.length; i++) {
    // 홀수 길이
    maxLength = Math.max(maxLength, expandFromMiddle(i, i));
    // 짝수 길이
    maxLength = Math.max(maxLength, expandFromMiddle(i, i + 1));
  }

  return maxLength;

  function expandFromMiddle(left, right) {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      left--;
      right++;
    }
    return right - left - 1;
  }
}