LeetCode 647: Palindromic Substrings Solution in Python – A Step-by-Step Guide

What Is LeetCode 647: Palindromic Substrings?

In LeetCode 647: Palindromic Substrings, you’re given a string s, and your task is to count all substrings that are palindromes—sequences that read the same forward and backward (e.g., "racecar", "aa"). A substring is any contiguous sequence of characters, and single characters count as palindromes too. For example, in s = "abc", the palindromic substrings are "a", "b", "c" (3 total), while in s = "aaa", they’re "a", "a", "a", "aa", "aa", "aaa" (6 total). The goal is to return the total count as an integer. This problem tests your ability to identify palindromes efficiently in a string.

Problem Statement

• Input:
• s: A string of characters.
• Output: An integer—total number of palindromic substrings.
• Rules:
• Palindrome: Reads same forward and backward.
• Substrings must be contiguous.
• Count all unique palindromic substrings.

Constraints

• 1 ≤ s.length ≤ 1000.
• s consists of lowercase English letters.

Examples

• Input: s = "abc"
• Output: 3 (Palindromes: "a", "b", "c")
• Input: s = "aaa"
• Output: 6 (Palindromes: "a", "a", "a", "aa", "aa", "aaa")
• Input: s = "a"
• Output: 1 (Palindrome: "a")

These examples set the string—let’s solve it!

Understanding the Problem: Counting Palindromes

To solve LeetCode 647: Palindromic Substrings in Python, we need to count every substring in s that’s a palindrome. A brute-force approach—checking all possible substrings—would be O(n³): O(n²) to generate substrings and O(n) to verify each, impractical for n ≤ 1000. Since palindromes expand symmetrically from centers, we can optimize with expansion or DP. We’ll use:

• Best Solution (Expand Around Center): O(n²) time, O(1) space—fast and efficient.
• Alternative Solution (Dynamic Programming): O(n²) time, O(n²) space—systematic but memory-heavy.

Let’s start with the expand-around-center solution, breaking it down for beginners.

Best Solution: Expand Around Center

Why This Is the Best Solution

The expand-around-center approach is the top choice for LeetCode 647 because it’s efficient—O(n²) time with O(1) space—and leverages the symmetry of palindromes by treating each character (and pair) as a potential center, expanding outward to count all matches. It fits constraints (n ≤ 1000) perfectly and is intuitive once you see the expansion in action. It’s like planting a palindrome seed and watching it grow!

How It Works

Think of this as a palindrome grower:

• Step 1: Iterate Centers:
• For each index i, consider two cases:
• Single center (e.g., "a" in "aba").
• Double center (e.g., "aa" in "baab").
• Step 2: Expand Around Center:
• From each center (i, i) or (i, i+1):
• Check if chars at left and right match.
• If yes, increment count, expand outward.
• Stop when mismatch or bounds reached.
• Step 3: Count Palindromes:
• Sum all expansions.
• Step 4: Return Result:
• Return total count.

It’s like a palindrome expander—grow and count!

Step-by-Step Example

Example: s = "aaa"

• Step 1: Centers:
• i=0: Single (a), Double (aa).
• i=1: Single (a), Double (aa).
• i=2: Single (a).
• Step 2: Expand:
• i=0, Single (0, 0): "a" (count += 1), expand to "aaa" (count += 1), total = 2.
• i=0, Double (0, 1): "aa" (count += 1), total = 3.
• i=1, Single (1, 1): "a" (count += 1), expand stopped, total = 4.
• i=1, Double (1, 2): "aa" (count += 1), total = 5.
• i=2, Single (2, 2): "a" (count += 1), total = 6.
• Step 3: Total count = 6.
• Output: 6.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass Solution:
    def countSubstrings(self, s: str) -> int:
        # Step 1: Initialize count
        count = 0

        # Step 2: Helper to expand around center
        def expand(left: int, right: int) -> int:
            local_count = 0
            while left >= 0 and right < len(s) and s[left] == s[right]:
                local_count += 1
                left -= 1
                right += 1
            return local_count

        # Step 3: Iterate over all possible centers
        for i in range(len(s)):
            # Single center (e.g., "a" in "aba")
            count += expand(i, i)
            # Double center (e.g., "aa" in "baab")
            count += expand(i, i + 1)

        # Step 4: Return total count
        return count

• Line 4: Init palindrome count.
• Lines 7-13: expand:
• Expand from left, right while chars match, count palindromes.
• Lines 16-19: Iterate:
• Count single-center (odd length) and double-center (even length) palindromes.
• Line 22: Return total.
• Time Complexity: O(n²)—n centers, O(n) expansion each.
• Space Complexity: O(1)—no extra space.

This is like a palindrome spotter—expand and tally!

Alternative Solution: Dynamic Programming

Why an Alternative Approach?

The dynamic programming (DP) approach builds a table of palindrome statuses—O(n²) time, O(n²) space. It’s more systematic, checking all substrings via a 2D array, but uses more memory and is less intuitive. It’s like mapping every possible palindrome in a grid!

How It Works

Picture this as a palindrome grid:

• Step 1: Init DP table:
• dp[i][j]: True if s[i:j+1] is palindrome.
• Step 2: Fill table:
• Single chars: dp[i][i] = True.
• Two chars: dp[i][i+1] = (s[i] == s[i+1]).
• Longer: dp[i][j] = (s[i] == s[j] and dp[i+1][j-1]).
• Step 3: Count palindromes from table.
• Step 4: Return count.

It’s like a palindrome mapper—grid and count!

Step-by-Step Example

Example: s = "aaa"

• Step 1: Init: dp = [[F,F,F], [F,F,F], [F,F,F]].
• Step 2: Fill:
• Singles: dp[0][0] = T, dp[1][1] = T, dp[2][2] = T, count = 3.
• Pairs: dp[0][1] = T, dp[1][2] = T, count = 5.
• Length 3: dp[0][2] = (a==a and dp[1][1]) = T, count = 6.
• Step 3: Total = 6.
• Output: 6.

Code for DP Approach

Copy codeclass Solution:
    def countSubstrings(self, s: str) -> int:
        # Step 1: Initialize DP table and count
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        count = 0

        # Step 2: Fill DP table
        for i in range(n):
            dp[i][i] = True  # Single char
            count += 1

        for i in range(n - 1):
            if s[i] == s[i + 1]:
                dp[i][i + 1] = True  # Two chars
                count += 1

        for length in range(3, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                if s[i] == s[j] and dp[i + 1][j - 1]:
                    dp[i][j] = True
                    count += 1

        # Step 3: Return total count
        return count

• Lines 4-6: Init DP table, count.
• Lines 9-18: Fill singles and pairs.
• Lines 20-26: Fill longer lengths.
• Time Complexity: O(n²)—fill table.
• Space Complexity: O(n²)—DP table.

It’s a grid counter—systematic but heavy!

Comparing the Two Solutions

• Expand Around Center (Best):
• Pros: O(n²) time, O(1) space, fast and minimal.
• Cons: Expansion logic less obvious.
• DP (Alternative):
• Pros: O(n²) time, O(n²) space, systematic.
• Cons: More memory, complex table.

Expand wins for efficiency.

Additional Examples and Edge Cases

• Input: s = "ab"
• Output: 2 ("a", "b").
• Input: s = "aabaa"
• Output: 9 ("a", "a", "b", "a", "a", "aa", "aa", "aba", "aabaa").

Both handle these well.

Complexity Breakdown

• Expand: Time O(n²), Space O(1).
• DP: Time O(n²), Space O(n²).

Expand is optimal.

Key Takeaways

• Expand: Center growth—smart!
• DP: Table clarity—clear!
• Palindromes: Counting is fun.
• Python Tip: Loops rock—see Python Basics.

Final Thoughts: Count Those Palindromes

LeetCode 647: Palindromic Substrings in Python is a fun string challenge. Expand-around-center offers speed and minimalism, while DP provides a structured alternative. Want more? Try LeetCode 5: Longest Palindromic Substring or LeetCode 516: Longest Palindromic Subsequence. Ready to spot? Head to Solve LeetCode 647 on LeetCode and count those palindromes today!