The problem
Count how many substrings (blocks of consecutive letters) of a string are palindromes. Blocks at different positions count separately.
Input: "abaab" Output: 8
Picture it
Same mirror trick: stand a mirror on every letter and between every pair of letters, then expand outward while the two sides match. Each successful expansion step is one more palindrome, so we add 1 to the count every time.
How to recognise it
- You must count substrings with a symmetry property, and substrings at different positions count separately (
"aaa"has 6). - A palindrome is symmetric about its centre, and shrinking one by a letter on each side leaves a palindrome.
- The string has up to 1,000 characters, so O(n²) is fine and O(n³) is borderline.
- The count can reach n(n + 1)/2, so you want a method that adds one per palindrome found, not one that lists them.
Start with brute force
Look at every substring and test whether it equals its reverse.
def count_brute(s):
n = len(s); total = 0
for i in range(n):
for j in range(i, n):
piece = s[i:j + 1]
if piece == piece[::-1]:
total += 1
return total
There are n(n + 1)/2 substrings and each test costs up to O(n), so time is O(n³): about 1.7 × 10^8 character comparisons for n = 1,000 (and more once slicing is counted). Space is O(n) for the slice.
From brute force to the idea
- Find the waste. Testing
s[i:j+1]ignores that its inside,s[i+1:j], was already known to be a palindrome or not. - Grow from the centre. Take a centre and widen
landrwhiles[l] == s[r]. Every successful widening is a new palindrome. - Two kinds of centre. Odd palindromes centre on a letter,
(c, c); even ones centre between letters,(c, c + 1). That makes 2n − 1 centres. - Count each step. Each time the ends match, add 1 to
countbefore widening. The first step counts the centre itself, the second the palindrome one letter wider, and so on until the match fails.
This is the key idea: every palindromic substring is found exactly once, as one step of the expansion from its own centre.
The key idea
Expand around every centre and count each successful step. O(n²).
Python solution
def count_substrings(s):
count = 0
for c in range(len(s)):
for l, r in ((c, c), (c, c + 1)): # odd and even centres
while l >= 0 and r < len(s) and s[l] == s[r]:
count += 1
l, r = l - 1, r + 1
return countIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n³): n² substrings, each compared in O(n) | O(n): the slice being tested |
| Expand around centres (shown code) | O(n²): 2n − 1 centres, each expands at most n/2 steps (worst for aaaa…) | O(1): a counter and two indices |
Edge cases
- Empty string: returns
0. - One letter (
"a"): returns1. - All different (
"abc"): returns3, only the single letters. - All the same (
"aaa"): returns6;"a" * 1000returns500500, which equals n(n + 1)/2 and is the largest possible count. - Even palindrome (
"abba"): returns6(four letters,"bb"and"abba"). - Repeated text counted separately (
"abab"): returns6;"a"and"b"each count twice, and"aba"and"bab"once each.
Common mistakes
- Using only odd centres, so
"abba"gives 4 instead of 6. - Counting distinct palindromes (a set of strings) instead of every occurrence, which is a different problem.
- Adding to
countafter the loop instead of inside it, so each centre contributes at most 1. - Skipping the bounds check, giving
IndexErroror wrong matches through negative indices.
Count only the palindromic substrings of length 2 or more. For "aaa" the answer is 3 ("aa" twice and "aaa"). Describe your approach, then write it if you like.
Compare with our answer
The same expansion works. Only a palindrome with at least two letters should be counted, which means r > l at the moment of counting.
def count_long(s):
count = 0
for c in range(len(s)):
for l, r in ((c, c), (c, c + 1)):
while l >= 0 and r < len(s) and s[l] == s[r]:
if r > l:
count += 1
l, r = l - 1, r + 1
return count
count_long("aaa") is 3 and count_long("abba") is 2. Time O(n²), space O(1). (Subtracting n from the original answer gives the same number.)
A strong answer mentions: both kinds of centre, counting inside the loop, the r > l test (or subtracting n, since every single letter is a palindrome), and the O(n²) worst case.
1. You must count how many substrings of a 1,000-character string are palindromes, counting repeats at different positions. Which approach fits best?
Each palindrome is counted once, at its own centre, in O(n²) total. Using a set removes repeats, which the problem wants counted, and pair counts or sorting ignore the order of the letters.
2. What is the time complexity of the shown code, and when is it worst?
For "aaaa…" each of the 2n − 1 centres expands about n/2 times. On a string with no matches each centre stops after one comparison, so the work is only O(n). The brute force is the cubic one.
3. What does the shown code return for "aaa"?
Three single letters, two "aa" pieces and one "aaa" make 6. A count of 3 would be the distinct strings (or only the single letters), and 9 would count every ordered pair of positions.
Score 60% or more and the lesson is marked complete.