Cursor frozen on “babad.” LeetCode 647. Palindromic substrings. Count ‘em all.
That’s the scene — late night, coffee cold, your brain mapping symmetries in a deceptively simple string. But here’s the thing: this problem isn’t about brute force. It’s an architectural gem, expand around centers, that flips string scanning on its head.
LeetCode 647 demands the total number of palindromic substrings in a given string. Single letters count (they’re trivially palindromic). So do “aa,” “aba.” For “babad,” it’s six: five singles plus “bab” and “aba.” Wait, actually seven if you tally evens right — but we’ll trace that.
Count the total number of palindromic substrings in a given string, where a palindromic substring reads the same forwards and backwards.
Pull that straight from the problem spec. Crystal clear. Yet solving it? That’s where the magic — or the grind — happens.
Why Centers? Not Ends.
Brute force? Check every substring. O(n³). Horrible. Dynamic programming tables? O(n²) time and space, fine but memory-hungry. Nah.
Expand around centers. Genius. Every palindrome has a center. Odds: one char. Evens: between two. For length n, 2n-1 possible centers. Boom — O(n²) total, since each expands at most n steps.
Take “aaa.”
Center at 0 (‘a’): expand left=-1 (stop), right=1 (‘a’== ‘a’), count 1 (“a”), then right=2 (‘a’==’a’), count 2 (“aaa”). Wait, no: the while loop counts each valid pair.
Look at the code.
def expandAroundCenter(left: int, right: int) -> int:
count = 0
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
count += 1 # Counts every expansion step as a palindrome
return count
Each iteration snags one palindrome. For “aaa,” center 0-0: first match (self), count 1; expand to -1/1 stop? No: initial left=0,right=0, s[0]==s[0], left=-1,right=1, count=1. Then while fails. But “aa” from 0-1? Wrong.
Hold up. For odd: i,i. Initial while: left=i,right=i, always equal, decrement left, increment right, count +=1. So counts the single char palindrome.
Then if expands further, counts longer ones.
For “aaa”: i=0, odd: left=0,right=0. Match, left=-1,right=1, count=1. Stop. So 1.
Even: i=0, left=0,right=1. s[0]==’a’==s[1], left=-1,right=2, count=1. Stop. 1.
i=1, odd: left=1,right=1, match, left=0,right=2, count=1 (since s[0]==s[2] after? Wait no: initial match self, then expand checks new left=0,right=2.
Let’s simulate properly.
String s=”aaa”, indices 0,1,2.
for i=0: odd: expand(0,0) while 0>=0,0<3,s0==s0: yes, left=-1,right=1, count=1 now while -1>=0? no. return 1 # “a” at 0
even: expand(0,1) while 0>=0,1<3,s0==s1 ‘a’==’a’: yes, left=-1,right=2, count=1 # “aa” 0-1 -1 no. return 1
total 2
i=1: odd: expand(1,1) 1>=0,1<3 equal, left=0,right=2, count=1 # single at 1 now while 0>=0,2<3,s0==s2 ‘a’==’a’: yes, left=-1,right=3, count=2 # now counts “aaa” too? Wait. Each count +=1 per layer. Initial: before first expand, count=0, check s1==s1, expand to 0,2, count=1 (this represents the palindrome from 1 to 1? No.
The count +=1 happens after confirming the current ends match, but before next expand.
It’s counting every concentric palindrome around the center.
For odd at 1: first iteration: ends 1,1 match, count=1 (length 1), expand to 0,2 Second: ends 0,2 match, count=2 (length 3), expand to -1,3 stop. So returns 2: the single and the full “aaa”.
Even at 1: left=1,right=2 s1==s2, count=1 (“aa” 1-2), expand 0,3: 0>=0,3<3? no.
i=2: odd expand(2,2): count=1 (single), expand1,3 no. Even(2,3): 3>=len no initial while.
Total: i0 odd1 even1 =2; i1 odd2 even1=3 total5; i2 odd1=1 total6.
“aaa” has 6: three singles, two “aa” (0-1,1-2), one “aaa”. Perfect. No double-counts because each palindrome is uniquely tied to its center.
How Does This Scale — And Where It Cracks?
O(n²). For n=1000, 10^6 ops. LeetCode green. Space O(1), just counters.
But my unique take: this mirrors Manacher’s O(n) algorithm — preprocess with separators, track radii. Manacher’s a beast, but harder to code live. Expand-around? Interview gold. It’s the accessible fractal explorer of strings — peel layers from centers, reveal nested symmetries like Matryoshka dolls.
Compare to longest pal substring (LeetCode 5): same trick, but track max length. Here, sum counts. Architectural shift? From global DP matrices to local expansions. Lighter, intuitive.
TraceLit visualizes this. Step every line. Watch left/right dance. But don’t sleep on manual traces — that’s where you internalize.
Example: “babad”
s = b a b a d 0 1 2 3 4
i=0 odd: center ‘b’, expands? only self. count1 i=0 even: b a no.
i=1 odd ‘a’: expand to b(0),b(2)? b==b yes, count2 (“bab”) Then -1,a(3) no. Even i1: a(1),b(2) no.
And so on. Totals 7.
Why LeetCode 647 Matters for Your Next Interview
It’s two pointers distilled. Patterns repeat: sliding windows, fast-slow. Master this, own strings.
Corporate hype? LeetCode calls it “Medium.” Try hard mode: explain without code. Or optimize to O(n) on spot — most freeze.
Prediction: With visual tools proliferating, interview prep evolves. No more whiteboard scribbles. Augmented reality traces? Coming. But core? Understand why centers work — every string’s symmetry orbits them.
Skeptical? Trace “abc.” Only 3 singles. No expansions. Clean.
“aabbcc” evens galore: each pair “aa”,”bb”,”cc.”
Is Expand Around Centers Always Optimal?
For counts, yes-ish. Manacher faster, but constant factors. Interviews favor simple.
Space? Pure. No hashmaps, no tables.
Deeper why: palindromes defined by reflection. Centers anchor reflections. Brute checks pairs; this radiates.
Why Does This Technique Dominate String Problems?
Reusability. Longest pal? Tweak return max. Radius? Track. It’s a Swiss army knife.
Historical nod: echoes 1970s string algorithms, but popularized in FAANG prep.
🧬 Related Insights
- Read more: 500 Rules Couldn’t Tame Claude Code—But Hooks Did, Here’s How
- Read more: React Labs February 2024: Shiny Progress or More Vaporware?
Frequently Asked Questions
LeetCode 647 solution explained?
Expand around 2n-1 centers, odd and even. O(n²) time, counts all layers per center.
How to count palindromic substrings efficiently?
Use two-pointer expansion from centers. Avoid DP for space. Code’s 15 lines.
Best visualizer for LeetCode palindromes?
TraceLit steps code visually. Free, interactive. Pairs with manual paper traces.
