277. Palindromic Substrings

Every palindrome has a center. There are 2n-1 possible centers (each character and each gap between characters); expand outward from each and count how far it stays a palindrome.

Key idea

A palindrome is defined by its center. A string of length n has 2n - 1 centers:

• n single-character centers (odd-length palindromes like aba).
• n - 1 between-character centers (even-length palindromes like abba).

From each center, expand two pointers l and r outward. Every time s[l] == s[r], the substring s[l..r] is a palindrome — count it — then keep expanding. Stop when the characters differ or a pointer falls off the string.

Walk-through

for each center:
    l, r = center endpoints
    while l >= 0 and r < n and s[l] == s[r]:
        count += 1
        l -= 1; r += 1

Worked example

s = "aaa":

• Odd center at 0: a ✓ (count 1).
• Odd center at 1: a ✓, expand aaa ✓ (count 3).
• Odd center at 2: a ✓ (count 4).
• Even center (0,1): aa ✓ (count 5).
• Even center (1,2): aa ✓ (count 6).

Total = 6.

Complexity

• Time: O(n²) — 2n-1 centers, each expanding up to O(n).
• Space: O(1).

class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        int count = 0;
        for (int i = 0; i < n; i++) {
            count += expand(s, i, i);       // odd-length centers
            count += expand(s, i, i + 1);   // even-length centers
        }
        return count;
    }

    private int expand(String s, int l, int r) {
        int cnt = 0;
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            cnt++;
            l--;
            r++;
        }
        return cnt;
    }
}