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.

Palindromic Substrings - LeetCode Solution

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.

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

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. Instead of verifying each substring independently, the algorithm expands from each center until the palindrome property breaks, counting all palindromes in a single pass per center.

Optimal Approach

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.

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.

Solution

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

1

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.

2

Expand Around Odd-Length Palindrome Centers

5for 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

Objective

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

Key Insight

Odd-length palindromes have a single center character. Starting with left and right pointers at the same index, expanding outward checks for symmetry. Each successful expansion corresponds to a valid palindrome, so the count increments. This process continues until a mismatch or boundary is reached, efficiently enumerating all odd-length palindromes centered at the current index.

Interview Quick-Check

Core Logic

Expanding pointers outward from the same index counts all odd-length palindromes centered there.

State & Boundaries

The expansion stops when pointers go out of bounds or characters at pointers differ.

Common Pitfalls & Bugs

Forgetting to check boundary conditions before accessing characters can cause index errors.

3

Expand Around Even-Length Palindrome Centers

12l, r = i, i + 1
13while l >= 0 and r < len(s) and s[l] == s[r]:
14    res += 1
15    l -= 1
16    r += 1

Objective

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

Key Insight

Even-length palindromes have two center characters. Initializing left and right pointers at adjacent indices allows expansion to detect palindromes like "aa" or "abba". Each successful expansion corresponds to a valid palindrome, incrementing the count. This approach complements the odd-length expansion to cover all palindrome types.

Interview Quick-Check

Core Logic

Expanding pointers outward from adjacent indices counts all even-length palindromes centered between them.

State & Boundaries

The expansion stops when pointers go out of bounds or characters at pointers differ.

Common Pitfalls & Bugs

Not handling even-length centers separately would miss palindromes like "aa".

4

Return Total Palindromic Substring Count

18	`return res`

Objective

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

Key Insight

After all expansions around every possible center, the result counter holds the total number of palindromic substrings. Returning this value completes the solution.

Interview Quick-Check

Core Logic

Returning the accumulated count provides the final answer to the problem.

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.

Line 6 Core

l, r = i, i

Set left and right pointers to the same index for odd-length palindrome expansion.

This initialization targets palindromes with a single center character, enabling symmetric expansion outward.

Line 8 Core

res += 1

Increment the palindrome count for each valid expansion.

Each successful expansion corresponds to a unique palindromic substring, so the count must increase accordingly.

Line 12 Core

l, r = i, i + 1

Set left pointer to current index and right pointer to next index for even-length palindrome expansion.

This initialization targets palindromes centered between two characters, capturing even-length palindromes missed by odd-length expansion.

Line 14 Core

res += 1

Increment the palindrome count for each valid even-length expansion.

Each successful expansion corresponds to a unique palindromic substring, so the count must increase accordingly.

Line 5 Core

for i in range(len(s)):

Iterate over each character index as a potential palindrome center.

Each index can serve as the center of odd-length palindromes and the left center of even-length palindromes, ensuring all palindromes are considered.

Line 9 Core

l -= 1

Move the left pointer one step left to expand the palindrome.

Expanding outward symmetrically checks larger substrings for palindrome property.

Line 10 Core

r += 1

Move the right pointer one step right to expand the palindrome.

Together with the left pointer, this expands the candidate substring to check for palindrome validity.

Line 15 Core

l -= 1

Move the left pointer one step left to expand the palindrome.

Expanding outward symmetrically checks larger substrings for palindrome property.

Line 16 Core

r += 1

Move the right pointer one step right to expand the palindrome.

Together with the left pointer, this expands the candidate substring to check for palindrome validity.

Line 18 Standard

return res

Return the total count of palindromic substrings found.

After all expansions, this value represents the complete count of palindromic substrings in the input string.

Line 3 Standard

res = 0

Initialize the palindrome count accumulator to zero.

Starting with zero ensures an accurate count of palindromic substrings as expansions find valid palindromes.

Test Your Understanding

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

Because every palindrome has a unique center (either a single character or a gap between characters), expanding from each center enumerates all palindromes without duplication or omission.

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`

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`

Problem

Example

Approach

Solution

Step-by-Step Solution

Initialize Result Counter

Expand Around Odd-Length Palindrome Centers

Expand Around Even-Length Palindrome Centers

Return Total Palindromic Substring Count

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.