public class Solution {
    /**
     * @param s: input string
     * @return: a string as the longest palindromic substring
     *
     * Solution: view this as Dynamic Programming
     * Solution: O(n^2)
     *
     */
    public String longestPalindrome(String s) {
        // check sanity first
        if (s == null || s.isEmpty()) {
            return "";
        }

        // initialize
        String result = "";
        String possibleResult = "";
        int len = s.length();
        boolean isP[][] = new boolean[len][len]; // Java all initialized to false by default

        // main code
        // odd base case (len == 1): isP[i][i+2] = isP[i+1][i+1] && ( s.charAt(i) == s.charAt(i+2) )
        for (int i = 0; i < len; i++) {
            int left = i;
            int right = i;
            isP[left][right] = true;

            // update result
            if (isP[left][right]) {
                result = giveFinalResult(result, s, left, right);
            }
        }
        // even base case (len == 2): isP[i][i+3] = isP[i+1][i+2] && ( s.charAt(i) == s.charAt(i+3) )
        for (int i = 1; i < len; i++) {
            int left = i-1;
            int right = i;
            if (s.charAt(left) == s.charAt(right)) {
                isP[left][right] = true;
            }

            // update result
            if (isP[left][right]) {
                result = giveFinalResult(result, s, left, right);
            }
        }

        // go - check & build at the same time from small to big
        for (int nowLen = 3; nowLen <= len; nowLen++) {
            int left = 0;
            int right = left + (nowLen - 1); // convert length to index concept
            while (true) {
                if (right >= len) break;

                isP[left][right] = isP[left+1][right-1] && (s.charAt(left) == s.charAt(right)); // DP

                // update result
                if (isP[left][right]) {
                    result = giveFinalResult(result, s, left, right);
                }

                left++;
                right++;
            }
        }

        // get result
        return result;
    }


    private String giveFinalResult(String nowResult, String s, int left, int right) {
        String result = nowResult;
        String possibleResult = s.substring(left, right+1);
        if (possibleResult.length() > result.length()) {
            result = possibleResult;
        }
        return result;
    }


}