Palindromic Substrings

mediumTrie & Strings43 stepsJava · Python · C++

Count every palindromic substring. Each palindrome has a centre: a character (odd length) or a gap between two characters (even length). Expand outward from all 2n−1 centres, counting each step while the ends match.

▶ Watch the animated trace

Traced input: s = "aaa" → 6. Original problem: neetcode.io/problems/palindromic-substrings

Complexity

BestO(n)

AverageO(n²)

WorstO(n²)

SpaceO(1)

Expansion stops at the first mismatch.

Key idea

2n − 1 centres: n single characters and n − 1 gaps.
Expand while s[l] == s[r]; each successful expansion is one more palindrome.
No extra space, unlike the DP table.

Common mistakes

Only checking odd-length centres misses "aa".
Counting distinct palindromes instead of all occurrences.

Solution

Java

int countSubstrings(String s) {
    int count = 0;
    for (int center = 0; center < 2 * s.length() - 1; center++) {
        int l = center / 2, r = l + center % 2;
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            count++;
            l--;
            r++;
        }
    }
    return count;
}

Python

def countSubstrings(s: str) -> int:
    count = 0
    for center in range(2 * len(s) - 1):
        l, r = center // 2, center // 2 + center % 2
        while l >= 0 and r < len(s) and s[l] == s[r]:
            count += 1
            l -= 1
            r += 1
    return count

C++

int countSubstrings(string s) {
    int count = 0, n = s.size();
    for (int center = 0; center < 2 * n - 1; center++) {
        int l = center / 2, r = l + center % 2;
        while (l >= 0 && r < n && s[l] == s[r]) {
            count++;
            l--;
            r++;
        }
    }
    return count;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
All distinct Only the single letters.	`s = "abc"`	`3`
Single character One palindrome.	`s = "z"`	`1`
Even palindrome a, b, b, a, bb, abba.	`s = "abba"`	`6`