Palindromic Substrings

35 min · countSubstrings()

The word aaa looks repetitive, but it hides six mirrored slices when positions matter. Three single letters, two copies of aa, and one aaa all count.

Given a lowercase string s, return the number of its palindromic substrings. A substring is one continuous slice of the original string, and a palindrome reads the same from left to right and right to left.

Count positions, not distinct text. If the same letters appear at two different start/end pairs, those are two separate substrings.

Constraints

1 <= s.length <= 1_000
s contains only lowercase English letters.
The answer is at most s.length * (s.length + 1) / 2, so it fits a 32-bit signed integer.

Hints

Start from intervals

You can choose every pair of boundaries and test whether the slice between them is a palindrome. What repeated work does that create?

Peel matching ends

s[left:right] is palindromic when its end characters match and the interval inside them is also palindromic. That relationship gives you a two-dimensional DP.

Every palindrome has a center

A palindrome grows symmetrically from either one character or the gap between two characters. Count each successful expansion across all 2n - 1 centers.

Follow-up

Can you keep O(n²) time while reducing the extra space from O(n²) to O(1)?

Visible cases

Examples

Example 1

ready

Input: s = "abc"
Expected: 3
Why: only the three one-character substrings are palindromes

Example 2

ready

Input: s = "aaa"
Expected: 6
Why: three singles, two position-distinct 'aa' slices, and one 'aaa'

Example 3

ready

Input: s = "a"
Expected: 1
Why: every single character is a palindrome

Interview signal

Asked at

AmazonGoogle

Check every substring

Choose every start and end position, then scan inward to test that interval. The helper uses indices rather than copying each slice, so the extra memory stays constant.

def count_substrings(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
    for left in range(len(s)):
        for right in range(left, len(s)):
            if is_palindrome(left, right):
                count += 1
    return count

Time O(n³): there are O(n²) intervals and an interval can take O(n) comparisons. Space O(1) beyond the call's local variables.

Palindrome DP — remember smaller intervals

Dynamic programming (DP) stores answers for smaller overlapping problems. Let is_pal[left][right] say whether the closed interval from left through right is a palindrome.

The end characters must match. Once they do, intervals of length 1 or 2 need no deeper proof; longer intervals also require the inside interval to be palindromic.

def count_substrings(s: str) -> int:
    n = len(s)
    is_pal = [[False] * n for _ in range(n)]
    count = 0
 
    for left in range(n - 1, -1, -1):
        for right in range(left, n):
            short = right - left <= 1
            if s[left] == s[right] and (short or is_pal[left + 1][right - 1]):
                is_pal[left][right] = True
                count += 1
 
    return count

Walking left backward guarantees that is_pal[left + 1][right - 1] is ready before you need it.

Time O(n²) because every interval is filled once. Space O(n²) for the boolean table.

Expand around centers — count palindromes as they grow

Every palindrome has exactly one center. Odd-length palindromes center on a character; even-length palindromes center on a gap. Expand while the two characters match and count one palindrome at every successful radius.

def count_substrings(s: str) -> int:
    def expand(left: int, right: int) -> int:
        found = 0
        while left >= 0 and right < len(s) and s[left] == s[right]:
            found += 1
            left -= 1
            right += 1
        return found
 
    count = 0
    for center in range(len(s)):
        count += expand(center, center)
        count += expand(center, center + 1)
    return count

No palindrome is missed, and none is counted twice: its midpoint chooses exactly one of those centers and its boundaries choose exactly one expansion radius.

Time O(n²) in the all-equal worst case, where many centers expand to the edges. Space O(1) beyond the counters and pointers.

Loading editor

Console

ready to run

Ready to run.

3 cases are queued.

Visible testcase

Case 1

Arguments · JSON arrays: string

Expected

Run: visible + custom · Submit: full suite