Skip to content

Volume ITechnology

4.23.6 — Palindromic Substrings ​

LeetCode 647 · Medium

The problem ​

Count how many substrings of s are palindromes. Substrings at different positions count separately even if they are identical.

"abc"   →  3     ("a", "b", "c")
"aaa"   →  6     ("a", "a", "a", "aa", "aa", "aaa")

Every single character is a palindrome, so the count is never below n.

Restating the Problem: Instead of finding the longest palindrome as we did in the previous problem, we now want to find the total number of palindromes hidden inside s. If the identical palindrome appears twice in different places, we count both occurrences.

Constraints to Note:

  • The string length is up to 1000. Again, this implies O(N^2) is perfectly acceptable.
  • s consists of lowercase English letters.

The brute force, and where it wastes work ​

The brute force way would be to generate all O(N^2) possible substrings and check each one to see if it reads the same forwards and backwards (an O(N) check). This means we would do an O(N) check O(N^2) times, leading to an O(N^3) time complexity. For N = 1000, this will TLE. Instead, we can use the exact same logic as "Longest Palindromic Substring" to optimize this down to O(N^2).

The pattern ​

4.23.5 with a counter instead of a length comparison.

Expand from all 2n − 1 centres. Every successful expansion step is one more palindrome, because each step widens the current palindrome by one character on each side, producing a new, longer palindrome centred at the same place.

So you do not need to measure anything at the end — just count the iterations of the expansion loops.

The solution ​

python
class Solution:
    def countSubstrings(self, s: str) -> int:
        total = 0  # (1)

        def expand(lo: int, hi: int) -> int:  # (2)
            count = 0
            while lo >= 0 and hi < len(s) and s[lo] == s[hi]:  # (3)
                count += 1                   # (4) each successful step is a palindrome
                lo -= 1
                hi += 1
            return count  # (5)

        for i in range(len(s)):  # (6)
            total += expand(i, i)            # (7) odd centres
            total += expand(i, i + 1)        # (8) even centres

        return total
ts
function countSubstrings(s: string): number {
  let total = 0;  // (1)

  function expand(lo: number, hi: number): number {  // (2)
    let count = 0;
    while (lo >= 0 && hi < s.length && s[lo] === s[hi]) {  // (3)
      count++;  // (4)
      lo--; hi++;
    }
    return count;  // (5)
  }

  for (let i = 0; i < s.length; i++) {  // (6)
    total += expand(i, i);  // (7)
    total += expand(i, i + 1);  // (8)
  }

  return total;
}

Line by line ​

(1) The running count of palindromic substrings.

(2) expand(lo, hi) counts the palindromes that share one centre.

(3) While both ends are inside the string and match,

(4) the stretch from lo to hi is a palindrome, so count it, then

(5) step both ends outward. When the ends stop matching, no wider stretch around this centre can be a palindrome either, so return the count.

(6) Try every position as a centre.

(7) Odd-length palindromes, centred on character i. The first step always counts, because a single character is a palindrome.

(8) Even-length palindromes, centred on the gap after i.

No off-by-one arithmetic at all, which makes this version cleaner than the "longest" one. You are counting iterations, not measuring a span, so the overshoot after the loop does not matter.

The odd expansion always counts at least 1 — a single character is a palindrome — so the total is automatically at least n.

The even expansion may count 0, when the two neighbouring characters differ.

Trace ​

"aaa"

centreexpansioncount
(0,0)a1
(0,1)aa1
(1,1)a, then aaa2
(1,2)aa1
(2,2)a1
(2,3)out of bounds0

Total 6 ✓ — three single characters, two "aa", one "aaa".

Edge cases ​

  • One character. One palindrome.
  • All the same letter, like "aaa". Every substring is a palindrome: 3 + 2 + 1 = 6.
  • All different letters. Only the single characters count, so the answer is the length.

Complexity ​

O(n^2) time, O(1) space.

Time Complexity Derivation: We loop through n characters, and for each, we test 2 centres (odd and even), making 2N - 1 centres in total. From each centre, the while loop can expand outward up to N/2 times in the worst case (e.g., "aaaaaa"). Therefore, (2N) \times (N/2) = N^2, so the time bound is O(N^2).

Space Complexity Derivation: We just keep an integer counter total. Inside expand, we use integer variables lo, hi, and count. There are no dynamic arrays, no hash maps, and no recursive call stack (since we don't recurse). Thus, O(1) auxiliary space.

The DP version ​

Same table as 4.23.5, counting the True cells:

python
n = len(s)
dp = [[False] * n for _ in range(n)]
total = 0
for j in range(n):
    for i in range(j, -1, -1):                   # i counts DOWN
        if s[i] == s[j] and (j - i < 2 or dp[i+1][j-1]):
            dp[i][j] = True
            total += 1
return total

O(n^2) time and O(n^2) space. Same reasoning as before: centre expansion is better here, but the table is what you want when you will query many substrings, as in 4.18.7 Palindrome Partitioning.

Where this goes next ​

  • Longest Palindromic Substring — the same expansion, tracking the maximum. 4.23.5.
  • Count Different Palindromic Subsequences — much harder: subsequences allow gaps, and distinct means duplicates must be excluded, which needs careful 2-D DP.
  • Manacher's algorithm gives the count in O(n) too, since the number of palindromes centred at a position is exactly its radius. 4.31.

What the interviewer will push on ​

"Why is every expansion step a new palindrome?" Each step produces a longer palindrome with the same centre, and different lengths are different substrings.

"How many centres?" 2n − 1, and be ready to justify the even ones.

"Do identical substrings at different positions count twice?" Yes — read the problem statement carefully. The distinct-substring version is a much harder problem.

"Can you do it in O(n)?" Manacher's, where the radius at each centre is the count.

One thing to volunteer: point out that this version avoids the off-by-one entirely, because counting iterations is simpler than measuring a span. Noticing when a small change makes code easier to get right is a good habit to show.

Next: 4.23.7 Decode Ways — back to the two-step recurrence, now with conditions on which steps are legal.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet