public class Solution {
    /**
     * @param s: input string
     * @return: a string as the longest palindromic substring
     */
    public String longestPalindrome(String s) {
        // write your code here
        String result = "";

        // check sanity first
        if (s == null || s.isEmpty()) {
            return "";
        }

        // main code
        int len = s.length();

        // extract certain part of original string as substrings
        for (int start = 0; start < len; start++) { // layer 1: O(n)
            for (int end = start; end < len; end++) { // layer 2: O(n)

                // verify if palindromic
                int left = start;
                int right = end;
                boolean isAllMateched = false;
                while (true) { // layer3: O(n)

                    if (left > right) {
                        isAllMateched = true;
                        break;
                    }

                    if (s.charAt(left) != s.charAt(right)) {
                        isAllMateched = false;
                        break;
                    }

                    left++;
                    right--;
                }

                // System.out.println("start: " +  start);
                // System.out.println("end: " +  end);

                // if all matched
                if (isAllMateched) {
                    String possibleResult = s.substring(start, end+1);
                    // check if longer
                    if (possibleResult.length() > result.length()) {
                        result = possibleResult;
                    }
                }
            }
        }

        // get result
        return result;
    }
}