class Solution {
  int left, maxLen;
  public void extendPalindrome(String s, int j, int k) {
    int len = s.length();
 
    // j, k가 문자열 길이의 범위내에 있고 j 인덱스의 문자와 k 인덱스의 문자가 같은 경우
    // j와 k를 이동시키면서 범위를 확장함
    while(0 <= j && k < len && s.charAt(j) == s.charAt(k)) {
      j --;
      k ++;
    }
 
    if(maxLen < k - j - 1) {
      left = j + 1;
      maxLen = k - j - 1;
    }
  }
  public String longestPalindrome(String s) {
    int len = s.length();
 
    if(len == 1) return s; // 글자 길이가 1인 경우 예외처리 
    
    for(int i = 0; i < len - 1; i ++) {
      extendPalindrome(s, i, i + 1); // 짝수 길이가 반복될 경우 Ex) abba
      extendPalindrome(s, i, i + 2); // 홀수 길이가 반복될 경우 Ex) aba
    }
 
    return s.substring(left, left + maxLen);
  }
}