Longest Palindromic Substring

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Solution

먼저 짝수와 홀수 경우로 나누어 생각하자

Odd case

i가 0부터 문자열 끝가지 움직여 가면서
i기준 왼쪽 과 오른쪽이 같은지를 확인한다.
동일하면 l은 왼쪽으로 r은 오른쪽으로 계속 이동 그렇지 않으면 멈춘다.
문자열의 길이는 r-l-1이다. (index가 0부터 시작하기 때문)

Even case

Odd case와 동일하나 초기화하는 것만 다름
l = i, r = i + 1

Code

class Solution {
    public String longestPalindrome(String s) {
        if(s.length() <= 1) return s;
        int max_len = 1;
        int n = s.length();
        int st =0, end = 0;

        //Odd length 
        for (int i=0; i <n-1; ++i) {
            int l = i, r = i;
            while(l >= 0 && r<n) {
                if(s.charAt(l) == s.charAt(r)) {
                    l--; r++;
                }else
                break; // 멈춘지점은 cbabf 처럼 palindrome에서
                       //양옆으로 한칸씩 더 움직인 상태이다

            }
            int len = r-l-1;
            if (len >max_len) {
                max_len = len;
                st = l +1; // 그래서 l은 오른쪽으로 한칸 이동시키고
                end = r-1; // r은 왼쪽으로 한칸 이동시켜
                           // bab와 같이 palindrome을 완성한다.
            }
        }

        //Even length
        for(int i =0; i < n-1; ++i) {
            int l = i, r = i+1;
            while(l >= 0 && r<n) {
                if(s.charAt(l) == s.charAt(r)) {
                    l--; r++;
                }else
                break;

            }
            int len = r-l-1;
            if (len >max_len) {
                max_len = len;
                st = l +1;
                end = r-1;
            }
        }
        return s.substring(st, end +1); //end는 우리가 0으로 초기화한
                                       //정수이고 index는 0부터 시작하므로
                                       //end + 1 해준다.

    }
}

출처: https://youtu.be/ZJUGtWObroc