A copy-desk preview paints the longest palindrome sitting inside a headline so writers can see the accidental symmetry. The first version nested every i..j slice, checked whether it read the same backwards, and kept the longest. A tweet-length title returned instantly. A pasted paragraph was still comparing slices when the preview timed out.

Return the longest contiguous palindromic substring of s. The answer is a window that already sits in s. A rearrangement of letters is a different prompt; a yes-or-no on a filtered phrase is a different prompt. If several windows share that length, any one of them is fine.

This is an interview writeup, not a two-pointers lecture. The two pointers post owns the left/right walk. Here we only care about which centers exist so even-length palindromes are not skipped.

The problem

Given a String s, return a longest contiguous substring that reads the same forwards and backwards. A single character is a palindrome; empty input returns empty.

s = "babad"  →  "bab"   (or "aba")
s = "cbbd"   →  "bb"
s = "a"      →  "a"

Note: Valid Palindrome is a filtered phrase — skip punctuation, fold case, then yes or no. Longest Palindrome rearranges letter counts so a palindrome could be built. This prompt wants a window already inside s. Do not recycle either proof.

Every slice is the honest brute force

For every pair i <= j, test whether s[i..j] is a palindrome and keep the longest. Two pointers on the slice, or a copied reverse of s.substring(i, j + 1). Correct. Cubic, and the copy pays an extra string per pair.

String longestNested(String s) {
    int n = s.length();
    if (n < 2) {
        return s;
    }
    int bestL = 0;
    int bestR = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            if (isPalindrome(s, i, j) && j - i > bestR - bestL) {
                bestL = i;
                bestR = j;
            }
        }
    }
    return s.substring(bestL, bestR + 1);
}

boolean isPalindrome(String s, int lo, int hi) {
    while (lo < hi) {
        if (s.charAt(lo) != s.charAt(hi)) {
            return false;
        }
        lo++;
        hi--;
    }
    return true;
}

At n = 20 this is a rounding error. At a pasted paragraph you paid a nested scan for a question expand answers in O(n²) with no table: a palindrome grows from its center.

Expand around 2n−1 centers

A palindrome is fixed by a center. Odd length: the center is a character (i, i). Even length: the center is the gap between i and i + 1. That is 2n − 1 centers, not n.

From each center, expand L left and R right while both stay in range and s.charAt(L) == s.charAt(R). When the pair fails, the last matching window is [L + 1, R - 1]. Track the best L, R.

Walk "babad" (odd winner), then "cbbd" (even winner):

s = b a b a d
    0 1 2 3 4
i=0 odd  (0,0)  "b"                 best=0..0
i=0 even (0,1)  b!=a
i=1 odd  (1,1)  a, then 0..2 b==b   best=0..2 "bab"
i=1 even (1,2)  a!=b
i=2 odd  (2,2)  b, then 1..3 a==a, 0..4 b!=d   "aba" length 3, tie keep "bab"
i=2 even (2,3)  b!=a
i=3, i=4        singles / failed gaps
return "bab"

s = c b b d
    0 1 2 3
odd centers are single letters
i=1 even (1,2)  b==b, then 0..3 c!=d   best=1..2 "bb"
return "bb"

The Java is that walk:

String longestPalindrome(String s) {
    int n = s.length();
    if (n < 2) {
        return s;
    }
    int bestL = 0;
    int bestR = 0;
    for (int i = 0; i < n; i++) {
        int[] odd = expand(s, i, i);
        int[] even = expand(s, i, i + 1);
        if (odd[1] - odd[0] > bestR - bestL) {
            bestL = odd[0];
            bestR = odd[1];
        }
        if (even[1] - even[0] > bestR - bestL) {
            bestL = even[0];
            bestR = even[1];
        }
    }
    return s.substring(bestL, bestR + 1);
}

int[] expand(String s, int L, int R) {
    while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
        L--;
        R++;
    }
    return new int[] {L + 1, R - 1};
}

Time is O(n²) — each of 2n − 1 centers expands at most O(n). Extra space is O(1) besides the two indexes and the returned substring.

Note: Skip even centers and “cbbd” returns a single letter. The two bs share a gap, not a character. After expand overshoots, the valid slice is L + 1 .. R - 1; returning L, R as-is is off by one. A failed even start (R already out of range) yields a negative length, and the > check leaves best alone.

What interviewers usually poke next

  • Several longest. "babad" allows "bab" or "aba". Return either. Do not sort them.
  • DP table. A boolean dp[i][j] for “is s[i..j] a palindrome?” matches the O(n²) time bound and spends O(n²) extra space you do not need. Expand is the usual board answer.
  • Count the slices. Palindromic Substrings uses the same expand and returns how many palindromic windows exist, not the longest one.
  • Null. Production would reject. At the board, ask.

You are done with this problem when you can say, out loud, why every slice is correct and cubic, why there are 2n − 1 centers instead of n, and why a DP table is the same bound with space you can skip.