Palindromic Substrings
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Count how many substrings of a string are palindromes (position-different substrings count separately).
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1How many centres does a string of length n have?
- Hint 2From a centre, when do you stop growing?
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
A mirror placed at a point of the word. From the mirror, compare the letter on the left with the letter on the right; if they match, one more palindrome is found and you step one place further from the mirror on both sides. As soon as they differ, the mirror at this place has nothing more. Try the mirror on every letter and in every gap between two letters.
- The obvious way
Check every substring for being a palindrome: O(n³).
- The key insight
For each of the 2n - 1 centres, set left and right pointers and expand while they are inside the word and the letters are equal, counting one palindrome per successful step. Total O(n²).
- The algorithm
- For each letter, expand with left = right = that letter (odd palindromes).
- Also expand with the right one place to the right (even palindromes).
- Each time the two ends match, count 1 and widen.
- Return the total.
Watch it run
Examples = "aaa"
Mirror on the first letter: "a" is one palindrome. It cannot grow (nothing on its left).
count = 1
Where people slip
- Do both odd and even centres, or "abba"-type palindromes are missed.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def count_substrings(s):
total = 0
def spread(left, right): # grow from a mirror while both sides match
found = 0
while left >= 0 and right < len(s) and s[left] == s[right]:
found += 1
left -= 1
right += 1
return found
for centre in range(len(s)):
total += spread(centre, centre) # mirror on a letter (odd length)
total += spread(centre, centre + 1) # mirror in a gap (even length)
return totalNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.