2주차. 문자열 조작(가장 긴 팰린드롬 부분 문자열)

05. 가장 긴 팰린드롬 부분 문자열
📌문제
가장 긴 팰린드롬 부분 문자열을 출력하라

  
- 예제1

  📝입력
  ` s = "babad"`

  💻출력
  `"bab"`
  
  
 - 예제2

  📝입력
  `s = "cbbd"`

  💻출력
  `"bb"` 

    
📌풀이
1. 중앙을 중심으로 확장 풀이 (23ms, 42.2mb)

 public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2)
            return s;

        for (int i = 0; i < len-1; i++) {
            extendPalindrome(s, i, i);  //홀수
            extendPalindrome(s, i, i+1); //짝수
        }
        return s.substring(start, start + maxLen);
    }

    private void extendPalindrome(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        if (maxLen < right - left - 1) {
            start = left + 1;
            maxLen = right - left - 1;
        }
    }

   - 본 풀이는 인터넷 서치를 참고하여 품...
   - extendPalindrome 함수를 두번 쓰는데 홀수로 체크하는 경우와 짝수로 체크하는 경우를 위해서
   - 왼쪽부터 점점 줄이고, 오른쪽은 점점 늘리는 방법으로 넓혀가며 팰린드롬을 체크함
   - 반복문을 돌면서 문자열의 0번 인덱스부터 끝까지 중앙을 중심으로 점점 넓여가는 방법