# 647. Palindromic Substrings

## Description

See: <https://leetcode.com/problems/palindromic-substrings/>

## Solution

This problem is similar to question 5 - ["Longest Palindromic Substring"](/cs-theory-and-problems/problems/leetcode/5.-longest-palindromic-substring.md). It uses the same [expand around the center](/cs-theory-and-problems/algorithms/sliding-window.md#expand-around-the-center) technique as that question to solve the problem.

Here, we need to find the number of substrings that are palindromic. Instead of iterating over each substring, we can use "expand around the center". So at each character, we decrement/increment the left and right pointers and check if the values are equal or not.

```python
class Solution:
    
    def expand_around_center(self, s: str, left: int, right: int) -> int:
        count = 0
        while left >= 0 and right < len(s) and s[left] == s[right]:
            count += 1
            left -= 1
            right += 1
        return count
             
    def countSubstrings(self, s: str) -> int:
        if len(s) == 1:
            return 1
        count = 0
        for index in range(len(s)):
            # we need to consider the two cases: 
            # i. odd length substrings where the mid char is one letter (i.e. "aba")
            # ii. even length substrings where there are two mid characters (i.e. "abba")
            count += self.expand_around_center(s, index, index)
            count += self.expand_around_center(s, index, index + 1)
        return count

"""
"a"
"aa"
"ab"
"abc"
"aaa"
"abba"
"aba"
"abaca"
"abbba"
"ababa"
"""
```

Time complexity: O(N^2).

Space complexity: O(1)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://monica-granbois.gitbook.io/cs-theory-and-problems/problems/leetcode/647.-palindromic-substrings.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.