Palindromic Substrings (LC 647)

Pattern: Expand Around Center
Difficulty: Medium
Key Concept: Each palindrome has a center; expand outward and count how many palindromes each center generates (usually 1 per successful expansion step).

Problem Statement

Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

Input

• s: String

Output

• int — count of palindromic substrings (each occurrence counts; overlaps allowed)

Example

• s = "abc" → 3 ("a", "b", "c")
• s = "aaa" → 6 ("a" three times, "aa" twice, "aaa" once)

---

1. Algorithm & Pseudocode

Brute force

Every substring s[i..j], test palindrome.

count = 0
for i from 0 to n-1:
    for j from i to n-1:
        if isPalindrome(s, i, j):
            count++
return count

Optimal

Expand around each center; each time you extend successfully, you found one new palindrome.

count = 0
for center from 0 to n-1:
    count += expand(s, center, center)     // odd length
    count += expand(s, center, center+1)   // even length
return count

expand(l, r):
    c = 0
    while l>=0 and r<n and s[l]==s[r]:
        c++
        l--; r++
    return c

---

2. Step-by-Step Analysis (Beginner-Friendly)

1. Why counting expansions works When l..r is valid, that substring is a palindrome. The next inward step would be shorter—actually we start at center and grow outward: first match counts length 1 or 2, each successful widen adds another palindrome.

2. Overlaps "aaa" has many overlapping "a" and "aa" substrings—each is counted separately.

3. Odd vs even centers Same reasoning as longest palindromic substring: cover both parity types.

4. Versus DP dp[i][j] boolean table also works in O(n²) but uses O(n²) memory unless optimized—expansion uses O(1) extra.

---

3. The Dry Run

Sample: s = "aaa".

center	type	expansions (each adds +1 to count)
0	odd	"a" at (0,0); then ( -1,1) invalid → +1
0	even	(0,1) all a → +1; (-1,2) invalid
1	odd	"a"; (0,2) "aaa" → +2 total at this center? trace carefully

Careful trace for index 1 odd:

• Start l=r=1: palindrome "a" → count 1
• Expand l=0,r=2: "aaa" → count 2

Index 0 odd: "a" only → 1
Index 0 even: "aa" at (0,1) → 1
Index 1 odd: "a", "aaa" → 2
Index 1 even: "aa" at (1,2) → 1
Index 2 odd: "a" → 1

Total: 1+1+2+1+1 = 6.

ASCII

aaa
 ^ odd center: a, aaa
^^ even center at gap: aa

---

4. Java Solution

Brute Force

class Solution {
    public int countSubstrings(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;
    }

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

Time: O(n³).
Space: O(1).

Optimal

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);
            count += expand(s, i, i + 1);
        }
        return count;
    }

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

Time: O(n²).
Space: O(1).

---

5. The “Java vs. Others” Edge

• Same expand helper as LC 5 Here you accumulate c++ per layer instead of tracking max length.
• Integer overflow Count fits in int for LeetCode constraints; for theoretical huge n, use long.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(n³)	O(1)	Triple loop / palindrome check.
Expand around center	O(n²)	O(1)	Standard interview solution.
Manacher	O(n)	O(n)	Linear-time count variant exists.