5. Longest Palindromic Substring

/**
 * Expand around center. Helper function returns the length of the palindrome.
 *
 * Time Complexity: O(N^2)
 *
 * Space Complexity: O(1)
 *
 * N = Length of the input string s.
 */
class Solution {
    public String longestPalindrome(String s) {
        if (s == null) {
            return "";
        }
        if (s.length() < 2) {
            return s;
        }
        int start = 0;
        int maxLen = 0;
        for (int i = 0; i < s.length() - 1; i++) {
            int len1 = extendPalindrome(s, i, i);
            int len2 = extendPalindrome(s, i, i + 1);
            if (maxLen < Math.max(len1, len2)) {
                start = len1 > len2 ? (i - len1 / 2) : (i - len2 / 2 + 1);
                maxLen = Math.max(len1, len2);
            }
        }

        return s.substring(start, start + maxLen);
    }

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

/**
 * Expand around center. Helper function returns the length of the palindrome.
 *
 * Time Complexity: O(N^2)
 *
 * Space Complexity: O(N)
 *
 * N = Length of the input string s.
 */
class Solution {
    public String longestPalindrome(String s) {
        if (s == null) {
            return "";
        }
        if (s.length() < 2) {
            return s;
        }

        String max = "";
        for (int i = 0; i < s.length() - 1; i++) {
            String s1 = extendPalindrome(s, i, i);
            String s2 = extendPalindrome(s, i, i + 1);
            if (s1.length() > max.length()) {
                max = s1;
            }
            if (s2.length() > max.length()) {
                max = s2;
            }
        }

        return max;
    }

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