LeetCode 647 - Palindromic Substrings

This Medium string problem asks for the total number of palindromic substrings within a given string. Instead of extracting and testing every possible substring, I used the expand-around-center technique to test all potential odd- and even-length palindrome centers directly.

---

Problem link and explanation

• Problem: 647. Palindromic Substrings
• Summary: Given a string s, return the number of palindromic substrings in it. Substrings with different start or end indices are counted as separate substrings even if they contain identical characters.

Brute-force slicing and testing every substring takes O(N³) time and generates many intermediate string objects. In contrast, expanding outwards from each center until characters mismatch tests only contiguous palindromic expansions and operates in constant extra memory.

---

Approach

Every palindrome centers around either a single character (odd length) or the gap between two adjacent characters (even length).

def expand_around_center(self, s: str, left: int, right: int) -> int:
    sub_count = 0

    while left >= 0 and right < len(s) and s[left] == s[right]:
        sub_count += 1
        left -= 1
        right += 1

    return sub_count

• The expand_around_center helper takes initial left and right indices and expands outward as long as s[left] == s[right], incrementing sub_count by 1 for each valid expansion step.
• The main loop iterates over all indices i from 0 to len(s) - 1, expanding around (i, i) for odd-length palindromes and (i, i + 1) for even-length palindromes.

---

Complexity analysis

• Time complexity: O(n²)
  • There are 2n - 1 possible centers, and each center expands at most O(n) steps outward.
• Space complexity: O(1)
  • Uses only pointer integers and counters without auxiliary tables or substrings.

---

Implementation code

class Solution:

    def expand_around_center(self, s: str, left: int, right: int) -> int:
        sub_count = 0

        while left >= 0 and right < len(s) and s[left] == s[right]:
            sub_count += 1
            left -= 1
            right += 1

        return sub_count

    def countSubstrings(self, s: str) -> int:
        count = 0

        for i in range(len(s)):
            count += self.expand_around_center(s, i, i)
            count += self.expand_around_center(s, i, i + 1)

        return count

---

Summary and reflection

Testing palindromes from the inside out is fundamentally faster than testing outside in, because any character mismatch immediately terminates further expansion for that center. Factoring out the expansion logic into a dedicated helper keeps the iteration loop concise and eliminates code duplication between odd and even centers.