{ }DevToolsDaily
ToolsInterview
Problems
New
CheatsheetsChat
New
BlogPricing
Ctrl + K

Palindromic Substrings – Solution & Complexity

Interview solutions
/
Palindromic Substrings

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. 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. 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. 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)Edit Distance solution (hard)Longest Palindromic Substring solution (medium)Longest Valid Parentheses solution (hard)Word Break solution (hard)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsContact Us © Monkey SkatesHave kids?