Longest Palindromic Substring: the idea to remember.

The core insight

Expand around each character and each gap, retaining the longest matching interval.

Why it works

Every palindrome has a character center or a gap center. Expanding all centers therefore considers every candidate longest palindrome.

The mistake to avoid

Even length palindromes need gap centers. The returned length after expansion is right minus left minus one.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

String longestPalindrome(String s) {
    int start = 0, best = 0;
    for (int i = 0; i < s.length(); i++) {
        int length = Math.max(expand(s, i, i), expand(s, i, i + 1));
        if (length > best) { best = length; start = i - (length - 1) / 2; }
    }
    return s.substring(start, start + best);
}
int expand(String s, int l, int r) {
    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { l--; r++; }
    return r - l - 1;
}

Make the next connection