Abstract / Summary

Count all substrings in a string that read the same forwards and backwards.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 73% (1+ million submissions).

Typical patterns to solve this problem:

• Dynamic Programming
• String
• Two Pointers

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a class Solution with a method countSubstrings that returns the number of palindromic substrings in a given string s. The algorithm iterates over each character, treating it as the center of potential odd-length palindromes, and also as the left boundary of possible even-length palindromes. For each center it expands outward while the characters match, incrementing a running total each time a palindrome is identified.

Core Logic

The method begins by initializing a counter result to zero and storing the length of the input string in size. The outer loop runs from i = 0 to i = size-1, selecting each position as a candidate center.

result = 0
size = len(s)
for i in range(size):

Odd-Length Expansion

For odd-length palindromes the left and right pointers start at the same index i. The algorithm counts the single-character palindrome immediately, then expands outward as long as the characters at the mirrored positions are equal and the pointers stay within bounds.

left = right = i
result += 1
while left > 0 and right < size - 1:
    left  -= 1
    right += 1
    if s[left] != s[right]:
        break
    result += 1

The while condition checks that there is room to move one step left and one step right. The break statement stops the expansion as soon as a mismatch is encountered, preventing unnecessary comparisons.

Even-Length Expansion

Even-length palindromes are handled by initializing left at i and right at i + 1. A guard clause skips the expansion entirely when the two adjacent characters differ or when right would exceed the string length.

left  = i
right = i + 1
if right == size or s[left] != s[right]:
    continue

If the adjacent pair matches, the pair itself forms a palindrome and is counted. The same outward expansion logic used for odd lengths then applies.

result += 1
while left > 0 and right < size - 1:
    left  -= 1
    right += 1
    if s[left] != s[right]:
        break
    result += 1

Finally, after processing all centers, the method returns the accumulated count.

return result

Edge Cases Handled

The algorithm gracefully handles an empty input string because size becomes zero, the for loop never executes, and result remains zero, which is the correct count. When the string consists of a single character, the outer loop runs once, the odd-length block counts the single character, and the even-length block is bypassed by the guard clause, yielding a result of one. For strings where all characters are identical, each center expands to the maximum possible radius, and the early break never triggers, ensuring that every possible palindrome is counted. When the string contains distinct characters with no repeating adjacent pairs, the even-length block is skipped for each index, and the odd-length block only counts the single-character palindromes, correctly returning the length of the string.

Performance Optimizations

The implementation incorporates several techniques that reduce unnecessary work. The immediate continue in the even-length section prevents the inner expansion loop from executing when the initial two-character window cannot form a palindrome, saving the cost of entering the loop. The while loops include boundary checks (left > 0 and right < size - 1) that avoid out-of-range indexing without requiring additional conditional statements inside the loop body. The use of a break statement as soon as a mismatch is detected stops further expansion for that center, ensuring that the algorithm does not continue to compare characters that are guaranteed not to be part of a palindrome. By counting the single-character palindrome directly (result += 1) before any expansion, the code eliminates the need for a separate check inside the loop for the base case. These choices collectively keep the inner work proportional to the actual length of each palindrome rather than the full length of the string.

Imagine that the letters in a word are like colorful building blocks lined up in a row. A palindrome is a special type of word that reads exactly the same way whether you start from the front or from the back, like the word radar. This code acts like a curious detective looking for all the hidden palindromes inside a long string of letters.

First, the code picks a spot in the middle of a word and looks outward to see if the letters on either side match. It starts by checking the single letter right in the middle, then carefully expands to the left and to the right, one step at a time, to see if it can find a matching pair. Every time it finds a matching pair, it adds one to the total count of palindromes found.

After searching for these odd-numbered groups that have a single middle letter, it does something similar for even-numbered groups. It looks at two letters right next to each other to see if they match, and then it expands outward to see if the neighbors further away also match. Just like before, it keeps counting every single time it finds a perfect match. By the time it finishes looking at every letter, it knows exactly how many of these special mirrored patterns are hidden inside the string.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python	Java							TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java		JS			Go		TS
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	BigEggStudy				C#
	black-shadows	C++
	bujosa		Python
	charles-wangkai			Java
	everthis					JS
	fartem							Ruby
	FelixFan1122				C#
	fengvyi	C++
	fpdjsns	C++
	fsq		Python
	gouthampradhan			Java
	halfrost								Go
	haoel	C++
	JoshCrozier					JS
	keineahnung2345	C++
	linouk23	C++
	lkwq007		Python
	MacJim	C++
	ruoru						Rust
	shreymehul				C#
	sonugiri1043	C++
	suxrobGM				C#
	varunu28			Java
	vli02									C
	vthwang			Java
	wisdompeak	C++
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
bujosa	Python
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
FelixFan1122	C#
fengvyi	C++
fpdjsns	C++
fsq	Python
gouthampradhan	Java
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
lkwq007	Python
MacJim	C++
ruoru	Rust
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
varunu28	Java
vli02	C
vthwang	Java
wisdompeak	C++
YuriSpiridonov	Python
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality