Palindromic Substrings — Expand Around Center

Problem

Return the number of palindromic substrings.

Example: "aaa" → 6 (a,a,a,aa,aa,aaa)

Approach — Expand Around Center

For each of the 2n-1 centers, expand outward while characters match. Count expansions.

Time: O(n²) | Space: O(1)

Solutions

Python

class Solution:
    def countSubstrings(self, s: str) -> int:
        n=len(s); count=0
        def expand(l,r):
            nonlocal count
            while l>=0 and r<n and s[l]==s[r]: count+=1; l-=1; r+=1
        for i in range(n):
            expand(i,i)    # odd length
            expand(i,i+1)  # even length
        return count

C++

class Solution {
    int expand(const string& s, int l, int r){
        int cnt=0;
        while(l>=0&&r<s.size()&&s[l]==s[r]){cnt++;l--;r++;}
        return cnt;
    }
public:
    int countSubstrings(string s){
        int n=s.size(),cnt=0;
        for(int i=0;i<n;i++){cnt+=expand(s,i,i);cnt+=expand(s,i,i+1);}
        return cnt;
    }
};

Java

class Solution {
    private int expand(String s, int l, int r){
        int cnt=0;
        while(l>=0&&r<s.length()&&s.charAt(l)==s.charAt(r)){cnt++;l--;r++;}
        return cnt;
    }
    public int countSubstrings(String s){
        int n=s.length(),cnt=0;
        for(int i=0;i<n;i++){cnt+=expand(s,i,i);cnt+=expand(s,i,i+1);}
        return cnt;
    }
}

Complexity

Time: O(n²) | Space: O(1)