5. Longest Palindromic Substring

O(n^2)

class Solution {
    public String longestPalindrome(String s) {
        String result = "";
        for (int i = 0 ; i < s.length(); i++) {
            result = helper(s, i, i, result);
            result = helper(s, i, i+1, result);
        }
        return result;
    }
    private String helper(String s, int l, int r, String result) {
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;
        }
        // when while ends, add l back, substract r back, l+1 r-1 (but substring's ending index needs put r-1+1)
        String cur = s.substring(l+1, r); 
        if (cur.length() > result.length()) {
            result = cur;
        }
        return result;
    }
}

/*

1. if check each substring
gen all substring(O(n^2)), check palindromic O(n)
=> O(n^3)

2. from each char (O(n)), treat it as the central (middle point) to 
check the substring is palindromic (two pointer) O(n), so O(n^2)
pointer move left and move right

move left  <-   middle . -> move right 

babad
_
 _   => 3
 spread in 

babad
  _.   => 3
<-
   ->

babad
   _  => 1
babad
    _.  => 1
    
this is odd length case,  (so left, right pointer start from same index, (i, i)

if it's a even length => our input become two differnt index (i, i+1)


*/