Palindromic Substrings (LeetCode 647)

The problem

Given a string s, count how many of its substrings are palindromes (read the same forwards and backwards). Substrings at different positions count separately, even if they’re the same text.

Input:  s = "aaa"
Output: 6

The palindromes are "a" three times, "aa" twice (positions 0–1 and 1–2), and "aaa" once: 3 + 2 + 1 = 6. For "abc" the answer is 3, just the single letters.

How to think about it

Start with brute force. List all O(n²) substrings and check each one for being a palindrome in O(n). That’s O(n³), too slow for n = 1000 (about a billion steps).

The key insight: every palindrome has a centre, and grows from it. If s[l..r] is a palindrome and s[l-1] == s[r+1], then s[l-1..r+1] is one too. And if s[l..r] is not a palindrome, no wider string with the same centre is. So stand at a centre and push two pointers outwards while the ends match. Every step outwards is one more palindrome. The moment they differ, stop: nothing wider from this centre can work.

There are 2n − 1 centres. Odd-length palindromes centre on a character (n of them). Even-length ones centre on the gap between two characters (n − 1 of them). The code loops over center from 0 to 2n − 2 and sets l = center // 2, r = l + center % 2: even values start at a single character, odd values at a pair.

Which pattern is this? Expand around centre, a two-pointer technique. The tell is “palindromic substrings”: palindromes are symmetric about a centre, so grow outwards rather than checking each substring from scratch. An O(n²) DP table also works, but needs O(n²) space.

Approach

1. Set total = 0.
2. For each center in 0 .. 2n − 2, set l = center // 2 and r = l + center % 2.
3. While l and r are in bounds and s[l] == s[r]: add one to total, then move l left and r right.
4. Return total.

Solution

def count_substrings(s):
    total = 0
    for center in range(2 * len(s) - 1):           # n chars + (n-1) gaps
        l = center // 2; r = l + center % 2        # odd centre: l == r; even: r == l+1
        while l >= 0 and r < len(s) and s[l] == s[r]:
            total += 1; l -= 1; r += 1             # each expansion is one palindrome
    return total
# count_substrings("abc") -> 3
# count_substrings("aaa") -> 6

Dry run

On s = "aaa" (five centres):

The middle centre expands twice, finding both "a" and "aaa". Final answer: 6.

Complexity

• Time: O(n²). There are 2n − 1 centres, and each expands at most O(n) steps. On a string like "aaaa…" that worst case is reached.
• Space: O(1). Only a few integers. Manacher’s algorithm gets O(n) time, but it is rarely expected in interviews.

Edge cases and pitfalls

• Empty string: range(-1) is empty, so the answer is 0.
• Forgetting even-length centres undercounts: "abba" has 6 palindromes, and "abba" itself and "bb" need the gap centres.
• Counting distinct palindromes is a different question. Here "a" at different positions counts each time.
• Off-by-one in the centre maths. With l = center // 2 and r = l + center % 2, center = 2n − 2 is the last character. Using range(2 * len(s)) would add a gap centre past the end; it happens to be harmless here because the bounds check fails, but it shows confused indexing.

Related problems

• Longest Palindromic Substring (LeetCode 5): the same expansion, keeping the longest instead of counting.
• Valid Palindrome (LeetCode 125): two pointers moving inwards instead of outwards.
• Palindrome Partitioning (LeetCode 131): uses palindromic substrings as building blocks.