Palindromic Substrings | Leetcode 647

Welcome to our multi-language deep dive on Palindromic Substrings (Leetcode 647). Unlike Longest Palindromic Substring which asks for the largest matching chunk, this problem asks you to calculate the aggregate total quantity of all identical palindromes hidden within a string.

Problem Statement

Given a string s, return the number of palindromic substrings in it. A string is a palindrome when it reads the same backward as forward. A substring is a contiguous sequence of characters within the string.

Example 1: s = "abc" => Output: 3 (Three palindromic strings: "a", "b", "c").

Example 2: s = "aaa" => Output: 6 (Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa").

Approach 1: 2D Dynamic Programming

If we use a 2D Truth-Table matrix dp, we can cache the internal results of substrings so we don't have to keep re-checking them.

dp[i][j] will be True if the substring mapped from index i to j is a palindrome.

A substring s[i:j] is guaranteed to be a palindrome dynamically IF and ONLY if:

1. s[i] == s[j] (The outer border characters match)
2. The inner substring itself s[i+1 : j-1] is also a matching palindrome!

We process from the shortest substrings (length 1) scaling upward!

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        count = 0
        dp = [[False] * n for _ in range(n)]
        
        # Base Case 1: Strings of 1 character are palindromes
        for i in range(n):
            dp[i][i] = True
            count += 1
            
        # Base Case 2: Double matching characters ("aa", "bb")
        for i in range(n - 1):
            if s[i] == s[i + 1]:
                dp[i][i + 1] = True
                count += 1
                
        # DP Expanding Range strings greater than 3!
        for length in range(3, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1  # Get End coordinate mapping
                
                # Check absolute endpoints && Check cached internal truth result
                if s[i] == s[j] and dp[i + 1][j - 1]:
                    dp[i][j] = True
                    count += 1
                    
        return count

Complexity Analysis

Approach 2: Expand Around Center Expansion O(1) Space

Can we bypass the massive matrix? Yes, using the incredibly dynamic Expand Around Center strategy. Instead of evaluating combinations externally, we execute a loop over each individual character, and treat that character explicitly as a perfectly symmetric mirror core center anchor location!

From every center, we shoot a left and right integer pointer incrementally outward simultaneously! If they match identically, we instantly aggregate the counter hit and expand outward again. Because a palindrome can theoretically be an Even length string ("aa") or Odd ("aba"), we intentionally execute two loops around every anchor coordinate!

graph TD
    A["s = 'abaab'"] --> B["Anchor Index 2 ('a')"]
    
    C{"Odd Setup"} --> D["l=2, r=2 ('a' == 'a')"]
    D --> E["l=1, r=3 ('b' == 'a' FALSE)"]
    
    F{"Even Setup"} --> G["l=2, r=3 ('a' == 'a')"]
    G --> H["l=1, r=4 ('b' == 'b')"]
    
    D -.->|1 Substring!| Z
    H -.->|2 Substrings!| Z

class Solution:
    def countSubstrings(self, s: str) -> int:
        count = 0
        n = len(s)
        
        def count_palindromes(left, right):
            hits = 0
            while left >= 0 and right < n and s[left] == s[right]:
                hits += 1
                left -= 1
                right += 1
            return hits
            
        for i in range(n):
            # Check Odd string expansion capabilities natively spanning off identical core index
            count += count_palindromes(i, i)
            # Check Even combinations expanding simultaneously off the neighboring chunk!
            count += count_palindromes(i, i + 1)
            
        return count

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (647)