{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Palindromic Substrings – Solution & Complexity

Interview solutions
/
Palindromic Substrings

Solution Walkthrough

  1. Step 1: Understand What Counts

    • Every substring that reads the same forwards and backwards counts, including all single characters.
    • Substrings at different positions are counted separately even if they look identical.
    • A brute-force check of every substring is O(n^3); we can do much better by growing palindromes from their centers.

  2. Step 2: Expand Around Each Center

    • A palindrome is defined by its center. A string of length n has 2n - 1 possible centers: n single-character centers (odd-length palindromes) and n - 1 between-character centers (even-length palindromes).
    • From a center, expand outward while the characters on both sides match. Each successful expansion is one more palindromic substring.
    def expand(s, left, right):
    count = 0
    while left >= 0 and right < len(s) and s[left] == s[right]:
        count += 1
        left -= 1
        right += 1
    return count

  3. Step 3: Sum Odd and Even Centers

    • For each index i, count odd-length palindromes centered at i (expand(i, i)) and even-length palindromes centered between i and i + 1 (expand(i, i + 1)).
    • Add the two counts for every index.
    def count_substrings(s: str) -> int:
    total = 0
    for i in range(len(s)):
        total += expand(s, i, i)      # odd length
        total += expand(s, i, i + 1)  # even length
    return total

  4. Step 4: Final Complete Solution

    • Expanding around every center visits each of the 2n - 1 centers and expands at most O(n) times, giving O(n^2) time.
    • Only a few counters are used, so the extra space is O(1).
    def count_substrings(s: str) -> int:
    def expand(left: int, right: int) -> int:
        count = 0
        while left >= 0 and right < len(s) and s[left] == s[right]:
            count += 1
            left -= 1
            right += 1
        return count

    total = 0
    for i in range(len(s)):
        total += expand(i, i)
        total += expand(i, i + 1)
    return total

FAQ

See also

Practice Palindromic Substrings online (run code in the browser)Decode Ways solution (medium)Edit Distance solution (hard)Longest Common Subsequence solution (medium)Longest Palindromic Substring solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?