How do you solve Palindromic Substrings?

Iterate over each index in the string, treating it as a center for odd-length palindromes, and also treat the gap between this index and the next as a center for even-length palindromes. For each center, expand pointers outward while characters match and count each valid palindrome found. This approach guarantees O(n^2) time and O(1) auxiliary space.

Palindromic Substrings

Q: What is the time complexity of Palindromic Substrings?

O(n^2). There are 2n - 1 possible centers (n single characters and n-1 gaps). For each center, expansion takes O(n) in the worst case, leading to O(n^2) total time.

Q: What pattern does Palindromic Substrings use?

The Pattern: Two Pointers (Expand Around Center) The Heuristic: Palindromes are symmetric around their center; by expanding pointers outward from each center and counting matches until a mismatch, the algorithm efficiently enumerates all palindromic substrings without redundant checks.

Medium Two Pointers

Problem

Given a string s, return the number of palindromic substrings in it.

1 ≤ s.length ≤ 1000
s consists of lowercase English letters.

Example

Input: s = "abc"

Output: 3

The palindromic substrings are "a", "b", and "c". Each single character is a palindrome. No longer palindromic substrings exist. Consider a more complex example: s = "aaa". The palindromic substrings are "a" (index 0), "a" (index 1), "a" (index 2), "aa" (indices 0-1), "aa" (indices 1-2), and "aaa" (indices 0-2), totaling 6. The algorithm iterates over each character as a potential palindrome center and expands outwards to count all palindromes centered at that position (odd length) and between positions (even length). This approach efficiently counts all palindromic substrings in O(n^2) time.

Approach

Straightforward Solution

A brute-force approach checks every substring and verifies if it is a palindrome, resulting in O(n^3) time complexity due to O(n^2) substrings and O(n) palindrome checks, which is inefficient for large inputs.

Core Observation

A palindrome mirrors around its center. Every palindrome can be expanded from its center outwards. Centers can be single characters (odd-length palindromes) or between two characters (even-length palindromes).

Path to Optimal

Preview

The key recognition signals are 'count palindromic substrings' and 'substring palindrome check'. These indicate the Two Pointers pattern because expanding around centers allows checking palindromes in O(n^2) time by avoiding repeated substring checks…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Iterate over each index in the string, treating it as a center for odd-length palindromes, and also treat the gap between this index and the next as a center for even-length palindromes…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n^2)

There are 2n - 1 possible centers (n single characters and n-1 gaps). For each center, expansion takes O(n) in the worst case, leading to O(n^2) total time.

Space

O(1)

Only a few integer variables are used for pointers and counters; no additional data structures scale with input size.

Pattern Spotlight

Two Pointers (Expand Around Center)

Palindromes are symmetric around their center; by expanding pointers outward from each center and counting matches until a mismatch, the algorithm efficiently enumerates all palindromic substrings without redundant checks.

Solution

Python

1class Solution:
  def countSubstrings(self, s: str) -> int:
      res = 0
      
      for i in range(len(s)):
          l, r = i, i
          while l >= 0 and r < len(s) and s[l] == s[r]:
              res += 1
              l -= 1
              r += 1
          
          l, r = i, i + 1
          while l >= 0 and r < len(s) and s[l] == s[r]:
              res += 1
              l -= 1
              r += 1
      
      return res

Step-by-Step Solution

Initialize Result Counter

3 res = 0

Objective

To set up a counter to accumulate the total number of palindromic substrings found.

Key Insight

A simple integer accumulator is sufficient to track the count. This variable is incremented each time a palindrome is detected during expansions. Initializing it to zero ensures accurate counting from scratch.

Interview Quick-Check

Core Logic

The result counter accumulates the count of all palindromic substrings found during expansions.

Expand Around Odd-Length Palindrome Centers

To count all palindromic substrings with a single character center by expanding pointers outward while characters match.

Expand Around Even-Length Palindrome Centers

To count all palindromic substrings with centers between two characters by expanding pointers outward while characters match.

Return Total Palindromic Substring Count

To return the accumulated count of all palindromic substrings found in the input string.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 7 Critical

while l >= 0 and r < len(s) and s[l] == s[r]:

Check palindrome validity while pointers are in bounds and characters match.

This condition ensures expansions only continue while the substring remains a palindrome, preventing invalid counts.

Line 13 Critical

while l >= 0 and r < len(s) and s[l] == s[r]:

Check palindrome validity while pointers are in bounds and characters match for even-length palindromes.

This condition ensures expansions only continue while the substring remains a palindrome, preventing invalid counts.

Full line-by-line criticality + rationale for all 13 lines available on Pro.

Test Your Understanding

Why does expanding around centers guarantee counting all palindromic substrings exactly once?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Palindromic Substrings from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Palindromic Substrings drill

or drill a free problem

1	`class Solution:`
2	`def countSubstrings(self, s: str) -> int:`
3	`res = 0`
4
5	`for i in range(len(s)):`
6	`l, r = i, i`
7	`while l >= 0 and r < len(s) and s[l] == s[r]:`
8	`res += 1`
9	`l -= 1`
10	`r += 1`
11
12	`l, r = i, i + 1`
13	`while l >= 0 and r < len(s) and s[l] == s[r]:`
14	`res += 1`
15	`l -= 1`
16	`r += 1`
17
18	`return res`