Problem statement

Given a string s, return the number of palindromic substrings in it. Substrings at different positions count separately, even when their text is equal.

Example 1

Input: s = "abc"
Output: 3
Explanation: "a", "b", "c".

Example 2

Input: s = "aaa"
Output: 6
Explanation: "a"×3, "aa"×2, "aaa".

Constraints

• 1 <= s.length <= 30
• s consists of lowercase English letters.

Hints for Palindromic Substrings

1. Hint 1

   Count palindromes by expanding around each of the 2n-1 centers.

2. Hint 2

   Every successful expansion step is one more palindrome.

How to solve Palindromic Substrings

Same centre-expansion as finding the longest palindrome, but instead of tracking a maximum you count every successful expansion. Each time the two ends still match, you have found one more palindromic substring around that centre.

Approach

1. For each of the 2n - 1 centres — every index, and every gap between adjacent indices — start with the two ends at the centre.
2. While both ends are in bounds and the characters match, increment the count and widen by one on each side.
3. Stop that centre when the ends disagree or run off the string.
4. The accumulated count is the answer.

Why it works

Every palindromic substring is symmetric about exactly one centre, so summing over all centres counts each substring once and none twice — the count is exact, not an approximation. And expansion around a centre enumerates its palindromes in increasing length: if a span of width w is a palindrome, so is every narrower span about the same centre, which is why each successful widening is a genuine new substring.

Complexity

• Time — O(n^2)
• Space — O(1)

Pitfalls

• Both centre kinds are needed — odd centres alone miss every even-length palindrome such as "aa".
• Count on each successful expansion, not once per centre.
• Identical substrings at different positions count separately, so no deduplication is wanted.
• Every single character is a palindrome, so the answer is never below n.

Reference solution

Python

def countSubstrings(s: str) -> int:
    count = 0
    for c in range(len(s)):
        for l0, r0 in ((c, c), (c, c + 1)):
            l, r = l0, r0
            while l >= 0 and r < len(s) and s[l] == s[r]:
                count += 1
                l -= 1
                r += 1
    return count

Java

public static int countSubstrings(String s) {
    int n = s.length(), total = 0;
    for (int i = 0; i < n; i++) {
        for (int mode = 0; mode < 2; mode++) {
            int l = i, r = i + mode;
            while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {
                total++;
                l--;
                r++;
            }
        }
    }
    return total;
}

C++

int countSubstrings(string s) {
    int n = (int) s.size(), total = 0;
    for (int i = 0; i < n; i++) {
        for (int mode = 0; mode < 2; mode++) {
            int l = i, r = i + mode;
            while (l >= 0 && r < n && s[l] == s[r]) {
                total++;
                l--;
                r++;
            }
        }
    }
    return total;
}

JavaScript

var countSubstrings = function(s) {
    let count = 0;
    for (let c = 0; c < s.length; c++) {
        for (const [l0, r0] of [[c, c], [c, c + 1]]) {
            let l = l0, r = r0;
            while (l >= 0 && r < s.length && s[l] === s[r]) { count++; l--; r++; }
        }
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Design a Food Rating System Medium
• Design Bitset Medium
• Iterator for Combination Medium
• Time Based Key-Value Store Medium
• Map Sum Pairs Medium
• Implement Magic Dictionary Medium