Palindromic Substrings
A medium Strings problem included in Love Babbar 450, Striver A2Z. Below: the roles whose interviews prioritise this topic, and how to practise it.
- Topic
- Strings
- Sheets
- 2
- Core for
- 13 roles
- Platform
- LeetCode
The problem
Given a string, count the total number of palindromic substrings.
Example 1
- Input
- "abc"
- Output
- 3
Example 2
- Input
- "aaa"
- Output
- 6
Example 3
- Input
- "abba"
- Output
- 6
Constraints
- 1 <= s.length <= 1000
- s consists of lowercase English letters
How to think about it
Updated 2026-09-09Every palindrome mirrors around its middle. A string of length n has exactly 2n - 1 possible centers: n single characters for odd lengths and n - 1 adjacent character gaps for even lengths. Growing outward symmetrically from each center counts every valid palindrome without ever re-evaluating inner substrings.
Approaches, worst first
Inspect all substrings
time O(n^3) · space O(1)
Extract every substring pair (i, j) and verify whether it reads identically forward and backward with a two-pointer check. It inspects O(n^2) substrings and spends O(n) validating each one independently.
Table dynamic programming
time O(n^2) · space O(n^2)
dp[i][j] marks whether s[i..j] is a palindrome, depending on s[i] == s[j] and dp[i+1][j-1]. Fills substrings in increasing order of length, eliminating redundant inner checks at the expense of an explicit 2D boolean grid.
Expand around centersWrite this one
time O(n^2) · space O(1)
Treat each index as an odd center (i, i) and each adjacent pair as an even center (i, i+1). Step two pointers outward as long as matching characters continue. Each successful expansion directly increments the running total while using zero auxiliary heap memory.
Where people lose marks · 3
- Neglecting even-length palindromes like 'abba' by only treating single characters as centers.
- Missing the baseline single-character palindromes. When s has length n, the answer is always at least n.
- Index out-of-bounds when stepping pointers outward past index 0 or index n - 1 before testing equality.
Full solution
Expand around each of the 2n - 1 centers: O(n^2) time with O(1) space, and one loop covers both odd and even lengths so the 'abba' case is never forgotten.
Python
def count_substrings(s: str) -> int:
n = len(s)
total = 0
# 2n - 1 centers: (i, i) for odd lengths, (i, i + 1) for even lengths
for center in range(2 * n - 1):
left = center // 2
right = left + center % 2
while left >= 0 and right < n and s[left] == s[right]:
total += 1
left -= 1
right += 1
return total
JavaScript
function countSubstrings(s) {
const n = s.length;
let total = 0;
// 2n - 1 centers: (i, i) for odd lengths, (i, i + 1) for even lengths
for (let center = 0; center < 2 * n - 1; center++) {
let left = Math.floor(center / 2);
let right = left + (center % 2);
while (left >= 0 && right < n && s[left] === s[right]) {
total++;
left--;
right++;
}
}
return total;
}
The theory behind it
Strings — the ground this problem stands on. All Strings problems
What Strings is
A string is an ordered necklace of text characters, like letters printed along a ribbon of paper. Each character sits at an exact numeric slot, holding a glyph such as a letter, punctuation mark, or digit. In many programming languages, ribbons cannot be edited after creation, meaning changing a single character requires pressing an entirely new ribbon from scratch.
When to reach for it
Reach for string techniques when inputs consist of words, DNA sequences, serialized data formats, or sentences. Clues include questions testing palindromes, anagram matches, substring patterns, parenthesis balancing, or character frequency counts. Whenever an algorithm asks to transform capitalization, parse structured tokens, or compute edits between two phrases, string representations are the core subject.
How the pattern works
Think of characters as small integer codes ranging across standard character sets. Frequency tables with fixed sizes often replace heavy hash maps when tallying occurrences. For search tasks, maintain rolling state using character indices or sliding borders. When building output text through repeated appends, accumulate pieces inside a mutable list or string builder rather than concatenating strings directly, avoiding quadratic copy overhead.
What each operation costs
| Operation | Time |
|---|---|
| read character by index | O(1) |
| concatenate two strings of total length n | O(n) |
| compare two strings of length n | O(n) |
What usually goes wrong with Strings
- Concatenating strings inside a loop using the plus operator, which silently creates full copies on each iteration and turns linear routines into quadratic slowdowns.
- Assuming all characters fall strictly within lowercase English letters without validating spaces, uppercase variants, punctuation marks, or multi-byte unicode symbols.
- Confusing substring length with end index when slicing, causing unexpected off-by-one truncations in languages that take length versus exclusive end position.
Which roles need this problem
Strings is a core topic for these 13 roles — if you're targeting one of them, this problem is early in your path, not optional.
Secondary for 7 more roles, including Data Engineer, Data Analyst, Embedded / Firmware Engineer.
Track this in your role's order
Pick your target role and all 370 problems — including this one — resequence to what that interview actually asks. Free.
Start freeMore Strings problems
Problem set and role mapping as of .