#104 Medium Time O(n²) Space O(1) Animated

Palindromic Substrings

Count the number of palindromic substrings.

LeetCode ↗

Tutor Mode Build the mental model before you memorize the code.

1 Predict
2 Trace
3 Explain
4 Implement

Pattern Dynamic programming: reuse smaller answers

Define one state whose value fully solves a smaller version of the problem.

Approach: Expand Around Center

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Core Insight

Define one state whose value fully solves a smaller version of the problem.

Common Pitfall

Write the recurrence in words before optimizing the storage.

Description

Count the number of palindromic substrings.

Constraints

Time Complexity: O(n²)
Space Complexity: O(1)

Solution — Expand Around Center

TimeO(n²) SpaceO(1)

Implementation Plan

Translate the invariant into these small, testable moves.

Define the state precisely.
Set base cases.
Fill states in dependency order.
Return the final state.

def countSubstrings(s):
    res = 0
    
    for i in range(len(s)):
        # odd length
        l = r = i
        while l >= 0 and r < len(s) and s[l] == s[r]:
            res += 1
            l -= 1
            r += 1
            
        # even length
        l = i
        r = i + 1
        while l >= 0 and r < len(s) and s[l] == s[r]:
            res += 1
            l -= 1
            r += 1
            
    return res

Longest Palindromic Substring

Decode Ways

Palindromic Substrings

Steps

Description

Constraints

Tags

Solution — Expand Around Center