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

Example function shape:

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

Examples

Example 1:

s = "abc"

The palindromic substrings are:

Output:

3

Example 2:

s = "aaa"

The palindromic substrings are:

Total:

3 + 2 + 1 = 6

Output:

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.

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:

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

For each index i, we check:

expand(i, i)

for odd-length palindromes.

And:

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

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:

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:

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:

count += 1

Then we expand outward:

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:

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).

Alternative Solution: Dynamic Programming

We can also use DP.

Let:

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.

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

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

Testing

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: