Skip to content

134 — Palindromic Substrings

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 4 revisions

134 — Palindromic Substrings

LeetCode 647 · Medium. Given a string s, return the number of palindromic substrings in it. A substring is a contiguous sequence of characters within the string.

🍽️ Intuition

This is the counting sibling of Longest Palindromic Substring, and it reuses the exact same center-expansion trick — the only difference is what you do with each successful expansion. Instead of asking "is this the widest palindrome so far?", you ask "how many times did expansion succeed at all?" Every center produces a sequence of nested palindromes as it expands outward ("a", then "bab", then "ababa", ...), and each one of those successful expansion steps is itself one more palindromic substring to count. Expand from every possible center, and add one to the tally every time the two sides still match.

🚩 Pattern-Recognition Cue

"Return the number of palindromic substrings" — when the ask shifts from "the longest one" to "how many total," and the underlying object is still palindromic substrings, that's the same expand-around-center machinery with a counter instead of a max-tracker.

🐢 Brute Force

Check every possible substring directly with an O(n) palindrome scan, incrementing a counter for each one that passes.

func countSubstringsBruteForce(_ s: String) -> Int {
    let chars = Array(s)
    let n = chars.count

    func isPalindrome(_ left: Int, _ right: Int) -> Bool {
        var l = left, r = right
        while l < r {
            if chars[l] != chars[r] { return false }
            l += 1
            r -= 1
        }
        return true
    }

    var count = 0
    for start in 0..<n {
        for end in start..<n {
            if isPalindrome(start, end) {
                count += 1
            }
        }
    }
    return count
}

// smoke test
print(countSubstringsBruteForce("abc"))     // 3
print(countSubstringsBruteForce("aaa"))     // 6

Big-O: O(n^3) time — O(n^2) substrings, each verified with an O(n) palindrome check in the worst case. O(n) space for the chars array.

🚀 Optimal

Expand outward from every possible center (both single-character and between-character), counting one palindromic substring for every successful expansion step until the match breaks.

func countSubstrings(_ s: String) -> Int {
    let chars = Array(s)
    let n = chars.count
    guard n > 0 else { return 0 }

    var count = 0

    func expand(_ left: Int, _ right: Int) {
        var l = left, r = right
        while l >= 0 && r < n && chars[l] == chars[r] {
            count += 1   // chars[l...r] is a palindrome — one more to the tally
            l -= 1
            r += 1
        }
    }

    for center in 0..<n {
        expand(center, center)         // odd-length palindromes
        expand(center, center + 1)     // even-length palindromes
    }

    return count
}

// smoke test — same cases as the brute force
print(countSubstrings("abc"))     // 3
print(countSubstrings("aaa"))     // 6

Big-O: O(n^2) time — 2n - 1 centers, each expansion taking up to O(n) steps in the worst case. O(n) space for the chars array, O(1) extra beyond that.

🔑 The Key Insight

Both versions ultimately verify the same set of palindromic substrings, but the brute force re-derives "is s[l...r] a palindrome?" from scratch for every one of the O(n^2) candidate substrings, even though a longer palindrome and all its inner palindromes share almost their entire comparison history. Expand-around-center exploits that shared structure directly: once chars[l] == chars[r] has been confirmed for the outermost pair, every successful expansion step is a newly discovered palindrome (the ones nested one layer in were already counted on the way out), so no substring's palindrome status is ever independently re-verified from its own two ends. The result is the same total palindrome count, produced by walking outward from 2n - 1 centers instead of independently validating O(n^2) substrings.

🔗 Related Chapters

  • 1D Dynamic Programming — same collapsed recurrence as Longest Palindromic Substring, isPal(l, r) = (s[l] == s[r]) && isPal(l+1, r-1), walked outward from every center and tallied instead of maximized.
  • Two Pointers — expand moves l and r outward in lockstep from a shared center, the same two-pointer expansion used throughout this chapter's sibling problem.
  • Arrays and Strings — Array(s) gives O(1) indexed access, the same string-to-array conversion every substring problem in this batch relies on.

🧸 Memory Sentence

Palindromic Substrings is Longest Palindromic Substring's counting twin — expand outward from every center, and every step that still matches is one more palindrome to add to the tally.

✅ Check Your Understanding

  1. For s = "aaa", list the 6 palindromic substrings the expected answer counts. Which centers and expansion steps produce each one?
  2. Why does expand increment count inside the while loop's body rather than only once after the loop finishes?
  3. Both this problem and Longest Palindromic Substring call expand(center, center) and expand(center, center + 1) for every center. What single change turns the "count" version's expand into the "longest" version's expand?

⬅️ Previous: Longest Palindromic Substring · Next: Decode Ways ➡️

Clone this wiki locally