Longest Palindromic Substring

1package pkg5leetcode.blind75;2 3/*4 * Longest Palindromic Substring | LC 55 * APPROACH: Expand around center for odd/even lengths.6 * COMPLEXITY: Time O(n^2), Space O(1)7 */8public class blind75_LC5LongestPalindromicSubstring {9    static String longestPalindrome(String s) {10        int start = 0, maxLen = 0;11        for (int i = 0; i < s.length(); i++) {12            int[] odd = expand(s, i, i);13            int[] even = expand(s, i, i + 1);14            int len = Math.max(odd[1] - odd[0], even[1] - even[0]);15            if (len > maxLen) {16                maxLen = len;17                start = len == odd[1] - odd[0] ? odd[0] : even[0];18            }19        }20        return s.substring(start, start + maxLen);21    }22 23    static int[] expand(String s, int lo, int hi) {24        while (lo >= 0 && hi < s.length() && s.charAt(lo) == s.charAt(hi)) { lo--; hi++; }25        return new int[]{lo + 1, hi};26    }27 28    public static void main(String[] args) {29        check(longestPalindrome("babad").equals("bab") || longestPalindrome("babad").equals("aba"), "case1");30        check(longestPalindrome("cbbd").equals("bb"), "case2");31        System.out.println("all tests passed");32    }33 34    static void check(boolean cond, String name) {35        if (!cond) throw new AssertionError("FAILED: " + name);36        System.out.println("  PASS " + name);37    }38}