(String, Medium) Longest Palindromic Substring

https://leetcode.com/problems/longest-palindromic-substring/description/

처음에 슬라이딩 윈도우 방식을 생각하고 고민해보다가 실패
왜? 단조성이 없다. 즉, left를 당겨서 조건에 맞는 윈도우 갱신을 할 수가 없음.
그것에 대한 기준이 없기 때문.

결국 최소 O(N^2)으로 풀어내야 하는 문제로 보인다.
계속 고민해봐도 모르겠어서 솔루션 참고함

핵심은

• left, right를 받아 가능한 범위 내에서 확장해나가기 (좌우로 넓혀도 팰린드롬이냐?)
• 이 때, 홀수로만 팰린드롬 체크하면 abba 같은 문자를 체크해낼 수 없으므로 i+1 해서 짝수 기준으로도 같이 체크해봐야 한다.
• 가장 긴 팰린드롬 서브스트링을 찾았으면 갱신하고 마지막에 리턴

while 조건을 보면 될때마다 계속 양옆으로 땡기므로 결국
left + 1과 right - 1 사이가 팰린드롬 서브스트링이 된다.

근데 String.substring 메서드 특성상 두 번째 인자는 포함 안하므로 아래와 같이 됨
s.substring(left + 1, right);

class Solution {
    public String longestPalindrome(String s) {

        if (s.length() < 2) {
            return s;
        }

        String max = s.substring(0, 1);

        for (int i=0; i<s.length(); i++) {
            String odd = expand(s, i, i);
            String even = expand(s, i, i + 1);

            if (odd.length() > max.length()) {
                max = odd;
            }
            if (even.length() > max.length()) {
                max = even;
            }
        }

        return max;
    }

    private String expand(String s, int left, int right) {
        int n = s.length();
        while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return s.substring(left + 1, right);
    }
}