A puzzle scorer awards one point for every palindromic window in the player’s string. The first version nested every i..j, checked the reverse, and added one. A three-letter guess returned instantly. A crossword-length fill was still comparing slices when the round timed out.

Count how many palindromic substrings sit in s. Single letters count. The answer is a number, not a window. Longest Palindromic Substring is the same expand; it keeps the longest slice. This prompt tallies every successful step.

This is an interview writeup, not a two-pointers lecture. The two pointers post owns the left/right walk. Here we only care about counting each matching expansion, including even-length gaps.

The problem

Given a String s, return how many contiguous palindromic substrings it contains. A single character is a palindrome. Empty input returns 0.

s = "abc"  →  3   ("a", "b", "c")
s = "aaa"  →  6   ("a", "a", "a", "aa", "aa", "aaa")
s = "a"    →  1

Note: Longest Palindromic Substring returns one longest window. This prompt returns a count. Do not recycle the best-slice indexes.

Nested slices are the honest brute force

For every pair i <= j, test whether s[i..j] is a palindrome and add one. Two pointers on the slice, or a copied reverse. Correct. Cubic, and the copy pays an extra string per pair.

int countNested(String s) {
    int n = s.length();
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            if (isPalindrome(s, i, j)) {
                count++;
            }
        }
    }
    return count;
}

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 crossword fill you paid a nested scan for a question expand answers in O(n²) with no table: each matching expansion is one palindrome.

Expand around 2n−1 centers

Longest Palindromic Substring already owns why there are 2n − 1 centers (odd: (i, i); even: (i, i + 1)) and how L/R overshoot. Do not rewrite that walk. The change is the return: increment on every successful expand step, then move out. Do not wait for the loop to fail and keep one best window.

Walk "aaa":

s = a a a
    0 1 2
i=0 odd  (0,0)  "a"                 count=1
i=0 even (0,1)  a==a  "aa"          count=2
i=1 odd  (1,1)  "a", then 0..2 a==a "aaa"   count=4
i=1 even (1,2)  a==a  "aa"          count=5
i=2 odd  (2,2)  "a"                 count=6
i=2 even (2,3)  R out of range
return 6

The six windows are three singles, two "aa"s, and one "aaa". The Java is that walk:

int countSubstrings(String s) {
    int n = s.length();
    int count = 0;
    for (int i = 0; i < n; i++) {
        count += expand(s, i, i);
        count += expand(s, i, i + 1);
    }
    return count;
}

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

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

Note: Skip even centers and “aaa” returns 4, not 6. The two "aa" windows live on gaps, not characters. Count inside the while, not after it: a failed even start (R already out of range) adds zero, which is correct.

What interviewers usually poke next

  • Longest window. Same centers, same expand. Longest Palindromic Substring keeps the best L, R instead of a counter.
  • Distinct strings. "aaa" has six occurrences and three distinct palindromes ("a", "aa", "aaa"). This prompt counts occurrences.
  • Null. Production would reject. At the board, ask.

You are done with this problem when you can say, out loud, why nested i..j is correct and cubic, why the expand is the LPS walk with a counter, and why skipping even centers drops the two "aa"s in "aaa".