# LeetCode 647: Palindromic Substrings

## Problem Restatement

We are given a string `s`.

We need to count how many substrings of `s` are palindromes.

A palindrome reads the same forward and backward.

A substring is a contiguous part of the string.

The same text can be counted multiple times if it appears at different positions. For example, in `"aaa"`, each `"a"` at each index is counted separately. The constraints are `1 <= s.length <= 1000`, and `s` consists of lowercase English letters.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A string `s` |
| Output | Number of palindromic substrings |
| Substring rule | Must be contiguous |
| Counting rule | Count by occurrence, not by distinct text |

Example function shape:

```python
def countSubstrings(s: str) -> int:
    ...
```

## Examples

Example 1:

```python
s = "abc"
```

The palindromic substrings are:

| Substring | Position |
|---|---|
| `"a"` | index `0` |
| `"b"` | index `1` |
| `"c"` | index `2` |

Output:

```python
3
```

Example 2:

```python
s = "aaa"
```

The palindromic substrings are:

| Substring | Count |
|---|---:|
| `"a"` | 3 |
| `"aa"` | 2 |
| `"aaa"` | 1 |

Total:

```python
3 + 2 + 1 = 6
```

Output:

```python
6
```

## First Thought: Check Every Substring

A direct solution is to generate every substring and check whether it is a palindrome.

There are `O(n²)` substrings.

Checking one substring can take `O(n)` time.

So the brute force solution takes `O(n³)` time.

```python
class Solution:
    def countSubstrings(self, s: str) -> int:
        def is_palindrome(left: int, right: int) -> bool:
            while left < right:
                if s[left] != s[right]:
                    return False
                left += 1
                right -= 1
            return True

        count = 0
        n = len(s)

        for left in range(n):
            for right in range(left, n):
                if is_palindrome(left, right):
                    count += 1

        return count
```

This is correct, but it does repeated work.

## Key Insight

Every palindrome has a center.

There are two kinds of centers:

| Palindrome Length | Center Type | Example |
|---|---|---|
| Odd | One character | `"aba"` centered at `"b"` |
| Even | Between two characters | `"abba"` centered between the two `"b"` characters |

So instead of checking every substring, we expand outward from every possible center.

For each index `i`, we check:

```python
expand(i, i)
```

for odd-length palindromes.

And:

```python
expand(i, i + 1)
```

for even-length palindromes.

Each successful expansion gives one palindromic substring.

## Algorithm

1. Initialize `answer = 0`.
2. For each index `i`:
   1. Count palindromes centered at `(i, i)`.
   2. Count palindromes centered at `(i, i + 1)`.
3. Return the total count.

The helper `expand(left, right)`:

1. While `left` and `right` are inside the string and `s[left] == s[right]`:
   1. Count one palindrome.
   2. Move `left` one step left.
   3. Move `right` one step right.
2. Return the count.

## Implementation

```python
class Solution:
    def countSubstrings(self, s: str) -> int:
        def expand(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

        answer = 0

        for i in range(len(s)):
            answer += expand(i, i)
            answer += expand(i, i + 1)

        return answer
```

## Code Explanation

The helper function expands around a center:

```python
def expand(left: int, right: int) -> int:
```

If `left == right`, the center is one character.

If `right == left + 1`, the center is between two characters.

The loop continues while the current substring is valid and palindromic:

```python
while left >= 0 and right < len(s) and s[left] == s[right]:
```

Each time the loop succeeds, `s[left:right + 1]` is a palindrome, so we add one:

```python
count += 1
```

Then we expand outward:

```python
left -= 1
right += 1
```

In the main loop, every index is used as both an odd center and the left side of an even center:

```python
answer += expand(i, i)
answer += expand(i, i + 1)
```

This covers all possible palindrome centers.

## Correctness

Every palindromic substring has a unique center.

If its length is odd, its center is one character. The algorithm counts it during `expand(i, i)` for that center index.

If its length is even, its center is between two adjacent characters. The algorithm counts it during `expand(i, i + 1)` for that center boundary.

For a fixed center, `expand` starts from the smallest possible palindrome at that center and grows outward while the characters remain equal. Each successful expansion corresponds to exactly one palindromic substring with that center.

The algorithm visits every possible odd and even center, so every palindromic substring is counted at least once. Since each palindrome has exactly one center, no palindrome is counted more than once.

Therefore, the returned count is exactly the number of palindromic substrings.

## Complexity

Let `n = len(s)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n²)` | Each center can expand up to `O(n)` positions |
| Space | `O(1)` | Only counters and pointers are stored |

## Alternative Solution: Dynamic Programming

We can also use DP.

Let:

```python
dp[left][right]
```

mean whether `s[left:right + 1]` is a palindrome.

A substring is a palindrome if:

1. Its two ends are equal.
2. The inside substring is also a palindrome, or its length is at most `2`.

```python
class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        answer = 0

        for right in range(n):
            for left in range(right + 1):
                if s[left] == s[right] and (right - left <= 2 or dp[left + 1][right - 1]):
                    dp[left][right] = True
                    answer += 1

        return answer
```

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n²)` | Checks every substring boundary |
| Space | `O(n²)` | Stores palindrome state for each substring |

The center expansion solution is usually preferred because it has the same time complexity and constant extra space.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.countSubstrings("abc") == 3
    assert s.countSubstrings("aaa") == 6
    assert s.countSubstrings("a") == 1
    assert s.countSubstrings("abccba") == 9
    assert s.countSubstrings("racecar") == 10
    assert s.countSubstrings("aaaa") == 10

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `"abc"` | Only single-character palindromes |
| `"aaa"` | Many overlapping palindromes |
| `"a"` | Minimum input |
| `"abccba"` | Even-length full palindrome |
| `"racecar"` | Odd-length full palindrome |
| `"aaaa"` | Every substring is a palindrome |