> For the complete documentation index, see [llms.txt](https://www.vjssn.dev/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://www.vjssn.dev/practice/24-06-06/lc647-palindromic-substrings.md).

# LC647 - Palindromic Substrings

## Problem

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.

### Example

**Input:** s = "abc"

**Output:** 3

**Explanation:** Three palindromic strings: "a", "b", "c"

## Solution

### Expand Palindrome from Centre

We take the solution from LC005 and build upon it. We check whether or not a substring is a palindrome from its center, and iterate across the characters in the string array, expanding outwards from each character to check whether or not it is a palindrome. For each expansion, we add one count to the number of palindromic substrings. Time complexity of this approach will be $$O(n^2)$$, and we don't use extra space so space complexity is $$O(1)$$.

```python
def expand(self, s: str, i, j):
	lbound = i
	rbound = j
	subcount = 0

	# expand if bounds don't reach end	
	while lbound >= 0 and rbound < len(s) and s[lbound] == s[rbound]:
	lbound -= 1
	rbound += 1
	subcount += 1
	
	# return number of palindromes found
	return subcount
	
def countSubstrings(self, s: str) -> int:
	odd = 0
	even = 0
	
	for i in range(len(s)):
		# expand for odd length palindromes
		odd += self.expand(s, i, i)
		# expand for even length palindromes
		even += self.expand(s, i, i + 1)
	
	return odd + even
```