LeetCode · #647

Palindromic Substrings Solution

Given a string s, return the number of palindromic substrings in it. Each single character is a palindrome.

01
Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #647

🏗️

Pattern

DP — expand around center

Given a string s, return the number of substrings that are palindromes. A substring is a contiguous sequence of characters. Different starting/ending positions count as different substrings even if the content is the same.

Example
Input: s = "aab" Output: 4 // "a", "a", "b", "aa" — four palindromic substrings
Constraints
• 1 ≤ s.length ≤ 1000 • s consists of lowercase English letters
02
Section Two · Approach 1

Brute Force — O(n³)

Check every substring: for each pair (i, j), check if s[i..j] is a palindrome by comparing characters from both ends. Count valid ones.

Why it works

Examining all O(n²) substrings and checking each in O(n) guarantees correctness. No palindrome is missed.

Why we can do better
Problem: O(n³) is too slow for n=1000. The expand-around-center approach eliminates the palindrome check: starting from each center, expand outward while characters match. Each expansion naturally discovers all palindromes rooted at that center, giving O(n²) total.
Java — O(n³) brute
class Solution { public int countSubstrings(String s) { int count = 0; for (int i = 0; i < s.length(); i++) for (int j = i; j < s.length(); j++) if (isPalin(s, i, j)) count++; return count; } private boolean isPalin(String s, int l, int r) { while (l < r) if (s.charAt(l++) != s.charAt(r--)) return false; return true; } }
Python — O(n³) brute
class Solution: def countSubstrings(self, s: str) -> int: count = 0 for i in range(len(s)): for j in range(i, len(s)): if s[i:j+1] == s[i:j+1][::-1]: count += 1 return count
MetricValue
TimeO(n³)
SpaceO(1)
03
Section Three · Approach 2

Expand Around Center — O(n²) time, O(1) space

A palindrome mirrors around its center. There are 2n - 1 possible centers: n on characters (odd-length) and n-1 between characters (even-length). Expand outward from each center while characters match, counting each valid expansion as a palindrome.

💡 Mental model: Drop a pebble at each position in the string (and between each pair). Ripples expand outward symmetrically. As long as the letters on both sides of the ripple match, the palindrome keeps growing — count every stage where the ripple is valid. You need 2n-1 drop points to cover all odd-length and even-length palindromes. Each expansion stops at the first mismatch — no wasted checks.
Algorithm
  • For each center c from 0 to 2n - 2:
  • left = c / 2, right = c / 2 + c % 2 (handles both odd and even centers).
  • While left ≥ 0 and right < n and s[left] == s[right]: count++, left--, right++.
  • Alternatively, call expand twice per index: once with (i, i) for odd, once with (i, i+1) for even.
🎯 When to recognize this pattern:
  • "Count palindromic substrings" or "find longest palindromic substring." The signal: substrings (contiguous) + palindrome check.
  • Expand-around-center is O(n²) with O(1) space — better than a 2D DP table (O(n²) space).
  • Also used in LC 5 (Longest Palindromic Substring). Manacher's algorithm gives O(n) but is rarely expected.
Why 2n-1 centers:
  • Odd-length palindromes center on a character (n choices).
  • Even-length palindromes center between two characters (n-1 choices). Total: 2n-1.
  • Each center generates at most n/2 expansions, but total work across all centers is O(n²).
04
Section Four · Trace

Visual Walkthrough

Trace for s = "aab". Expected: 4 palindromic substrings.

Palindromic Substrings — Expand Around Center (s="aab")
5 centers: 3 on chars (odd) + 2 between chars (even). Expand from each. String: a a b Index: 0 1 2 Center (0,0) odd: s[0]='a' → palindrome "a". count=1. Expand: l=-1 → stop. Center (0,1) even: s[0]='a'==s[1]='a' → palindrome "aa". count=2. Expand: l=-1 → stop. Center (1,1) odd: s[1]='a' → palindrome "a". count=3. Expand: s[0]='a'≠s[2]='b' → stop. Center (1,2) even: s[1]='a'≠s[2]='b' → no palindrome. count=3. Center (2,2) odd: s[2]='b' → palindrome "b". count=4. Expand: r=3 → stop. return 4 ✓
05
Section Five · Implementation

Code — Java & Python

Java — Expand around center
class Solution { int count = 0; public int countSubstrings(String s) { for (int i = 0; i < s.length(); i++) { expand(s, i, i); // odd-length palindromes expand(s, i, i + 1); // even-length palindromes } return count; } private void expand(String s, int l, int r) { while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { count++; // valid palindrome found l--; r++; // expand outward } } }
Python — Expand around center
class Solution: def countSubstrings(self, s: str) -> int: count = 0 def expand(l: int, r: int) -> int: c = 0 while l >= 0 and r < len(s) and s[l] == s[r]: c += 1; l -= 1; r += 1 return c for i in range(len(s)): count += expand(i, i) # odd count += expand(i, i + 1) # even return count
06
Section Six · Analysis

Complexity Analysis

ApproachTimeSpaceTrade-off
Brute force (check all substrings)O(n³)O(1)Simple but cubic
2D DP tableO(n²)O(n²)Same time, but O(n²) space for dp table
Expand around center ← optimalO(n²)O(1)No extra space; natural palindrome discovery
Manacher's O(n) exists but is rarely expected in interviews. Expand-around-center at O(n²) is the standard answer. Manacher's reuses previously computed palindrome extents to avoid redundant expansions — elegant but complex to code correctly.
07
Section Seven · Edge Cases

Edge Cases & Pitfalls

CaseInputWhy It Matters
Single char"a"1 palindrome. Expand finds it immediately.
All same"aaaa"n + (n-1) + … + 1 = n(n+1)/2 = 10 palindromes for n=4.
No multi-char palindromes"abc"Only 3 single-char palindromes. All even-center expansions fail.
Even-length palindrome only"ab"2 single chars. No even-length match ('a'≠'b').
Long palindrome"racecar"Entire string is palindrome. Center at index 3 expands to full string.
⚠ Common Mistake: Forgetting even-length palindromes — only calling expand(i, i) for odd-length. Even-length palindromes like "aa" or "abba" are only discovered by expand(i, i+1). Always call expand twice per index: once for odd, once for even.

← Back to DP — 1D problems