Palindromic Substrings

Problem Description

Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

Examples

Constraints

• 1 ≤ s.length ≤ 1000
• s consists of lowercase English letters.

Counting Symmetric Extensions from Centers

Like the “Longest Palindromic Substring” problem, checking each substring independently takes O(n³) time.

We optimize by using center expansion. Each center represents a possible palindrome symmetry point.

• For each center (left, right), we expand outward as long as boundary characters match.
• For every step we can successfully expand, we have discovered a new valid palindromic substring. We simply increment our counter by one for each successful match and keep expanding.

Because every successful expansion step corresponds to exactly one distinct palindrome, the total count of valid expansions equals the total number of palindromic substrings.

Solution 1: Expand Around Center

Iterate through all possible centers (odd and even), incrementing the global count on every successful matching expansion step.

class Solution {
    public int countSubstrings(String s) {
        if (s == null || s.length() == 0) return 0;

        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            count += expand(s, i, i);     // odd-length center
            count += expand(s, i, i + 1); // even-length center
        }
        return count;
    }

    private int expand(String s, int left, int right) {
        int count = 0;
        // increment count for every matching character boundary
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            count++;
            left--;
            right++;
        }
        return count;
    }
}

class Solution:
    def countSubstrings(self, s: str) -> int:
        if not s:
            return 0

        count = 0

        def expand(left, right):
            local_count = 0
            # increment count for every matching character boundary
            while left >= 0 and right < len(s) and s[left] == s[right]:
                local_count += 1
                left -= 1
                right += 1
            return local_count

        for i in range(len(s)):
            count += expand(i, i)  # odd-length center
            count += expand(i, i + 1)  # even-length center

        return count

#include <string>

class Solution {
private:
    int expand(const std::string& s, int left, int right) {
        int count = 0;
        // increment count for every matching character boundary
        while (left >= 0 && right < s.length() && s[left] == s[right]) {
            count++;
            left--;
            right++;
        }
        return count;
    }

public:
    int countSubstrings(std::string s) {
        if (s.empty()) return 0;

        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            count += expand(s, i, i);     // odd-length center
            count += expand(s, i, i + 1); // even-length center
        }
        return count;
    }
};

Complexity Analysis:

• Time Complexity: O(n²) where n is the length of string s. There are 2n - 1 centers, and each expansion takes at most O(n) steps.
• Space Complexity: O(1) auxiliary space as we do not use temporary matrices or structures.

Where it breaks: Nothing breaks for standard input sizes. On very large strings, Manacher’s algorithm can reduce time to O(n), but the constraint limit of 1000 characters makes the O(n²) solution highly efficient.

Common Mistakes

• Not checking even-length centers. If you omit the expand(i, i + 1) check, you will miss all even-length palindromes (like "aa" inside "aaa").
• Evaluating out-of-bounds array indices. Ensure left >= 0 and right < s.length() checks occur before dereferencing characters inside the loop.
• Adding the length of expansion instead of the step count. Each valid step adds exactly 1 to the count, not the difference of indices.

Frequently Asked Questions

Are single characters considered palindromes? Yes. Any single character (e.g. 'a') is symmetric, so it counts as a palindrome. The odd center checks expand(i, i) handle this on their first step.

How does the space complexity compare to dynamic programming? The DP solution uses an O(n²) boolean table to store whether s[i..j] is a palindrome. Center expansion uses O(1) space, making it much more memory efficient.

What does this problem test in interviews? It tests your ability to adapt symmetric expansion techniques to counting problems without allocating extra memory matrices.

← All Problems