leetcode-647 Palindromic Substrings

# Given a string s, return the number of palindromic substrings in it.
#
# Example 1:
# Input: s = "abc"
# Output: 3
# Explanation: "a", "b", "c"
#
# Example 2:
# Input: s = "aaa"
# Output: 6
# Explanation: "a", "a", "a", "aa", "aa", "aaa"
#
# Constraints:
# 1 <= s.length <= 1000

class Solution:
    # Approach 1: Expand Around Center
    def countSubstrings(self, s: str) -> int:
        count = 0

        def expand_around_center(left, right):
            nonlocal count
            while left >= 0 and right < len(s) and s[left] == s[right]:
                count += 1
                left -= 1
                right += 1

        for i in range(len(s)):
            # Odd length palindromes (center is single char)
            expand_around_center(i, i)
            # Even length palindromes (center is between two chars)
            expand_around_center(i, i + 1)

        return count

    # Approach 2: Dynamic Programming
    def countSubstrings2(self, s: str) -> int:
        n = len(s)
        # dp[i][j] = True if s[i:j+1] is palindrome
        dp = [[False] * n for _ in range(n)]
        count = 0

        # Every single character is a palindrome
        for i in range(n):
            dp[i][i] = True
            count += 1

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

        # Check for lengths 3 to n
        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

        return count

# Expand Around Center: Time O(n^2), Space O(1)
# DP: Time O(n^2), Space O(n^2)
#
# Expand Around Center Algorithm:
# 1. For each position, try it as center
# 2. Expand outward while characters match
# 3. Count each valid palindrome found
# 4. Handle both odd and even length palindromes
#
# Why two expand calls per position?
# - Odd length: center is at index i (e.g., "aba")
# - Even length: center is between i and i+1 (e.g., "abba")
#
# Related Problems:
# - Longest Palindromic Substring (LC 5) - track max length
# - Palindrome Partitioning (LC 131) - backtracking
#
# AirBnB: Tests string manipulation and palindrome patterns