Palindromic Substrings

MediumStrings

Count how many substrings of s are palindromes, counting each occurrence separately.

Constraints

1 <= s.length <= 1000
s consists of lowercase letters

Expand around center

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

Every palindrome has a center. Expand outward from each of the 2n-1 centers and count each successful expansion as one palindromic substring.

#include <bits/stdc++.h>
using namespace std;

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