Problem Description

Given a string s, you are asked to return the total number of palindromic substrings in s. A substring is a contiguous sequence of characters within the string. A substring is called a palindrome if it reads the same forward and backward.

• Each substring with different start or end indices is considered a different substring, even if they consist of the same characters.
• Single characters are considered palindromic substrings.
• Constraints: 1 <= s.length <= 1000

Example:
Input: s = "abc"
Output: 3
Explanation: Each character is a palindrome: "a", "b", "c".

Thought Process

The most direct way to solve this problem is to check every possible substring in s and see if it's a palindrome. For a string of length n, there are about O(n^2) possible substrings. For each substring, we can check if it's a palindrome by comparing characters from both ends moving towards the center.

However, this brute-force approach is inefficient because it repeatedly checks overlapping substrings and recalculates the same palindromic checks. We need an optimized way to avoid redundant work.

An important insight is that every palindrome "expands" from its center. For a string, there are 2n - 1 possible centers (each character and the gap between characters), and we can expand around each center to count all palindromic substrings. This method avoids recalculating palindromes and is much more efficient.

Solution Approach

We use the "Expand Around Center" technique to efficiently count all palindromic substrings:

• Step 1: For each index in the string, treat it as the center of a possible palindrome.
• Step 2: For each center, expand outward as long as the substring remains a palindrome (i.e., the characters on both sides are equal).
• Step 3: Consider both odd-length palindromes (centered at a character) and even-length palindromes (centered between two characters).
• Step 4: For every successful expansion, increment a counter.
• Step 5: Return the total count after checking all centers.

This approach ensures we count every palindromic substring exactly once and never check the same substring more than necessary.

Example Walkthrough

Let's walk through the example s = "aba":

• Center at index 0 ("a"): Expands to "a" (palindrome).
• Center between 0 and 1 ("ab"): Not a palindrome.
• Center at index 1 ("b"): Expands to "b" (palindrome), then expands further to "aba" (palindrome).
• Center between 1 and 2 ("ba"): Not a palindrome.
• Center at index 2 ("a"): Expands to "a" (palindrome).

So, the palindromic substrings are: "a", "b", "a", "aba". The total count is 4.

Code Implementation

class Solution:
    def countSubstrings(self, s: str) -> int:
        def expandAroundCenter(left, right):
            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 center in range(len(s)):
            total += expandAroundCenter(center, center)     # Odd length
            total += expandAroundCenter(center, center + 1) # Even length
        return total
      

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.length(), total = 0;
        for (int center = 0; center < n; ++center) {
            total += expandAroundCenter(s, center, center);     // Odd length
            total += expandAroundCenter(s, center, center + 1); // Even length
        }
        return total;
    }
private:
    int expandAroundCenter(const string& s, int left, int right) {
        int count = 0, n = s.length();
        while (left >= 0 && right < n && s[left] == s[right]) {
            ++count;
            --left;
            ++right;
        }
        return count;
    }
};
      

class Solution {
    public int countSubstrings(String s) {
        int total = 0;
        for (int center = 0; center < s.length(); center++) {
            total += expandAroundCenter(s, center, center);     // Odd length
            total += expandAroundCenter(s, center, center + 1); // Even length
        }
        return total;
    }
    private int expandAroundCenter(String s, int left, int right) {
        int count = 0;
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            count++;
            left--;
            right++;
        }
        return count;
    }
}
      

var countSubstrings = function(s) {
    let total = 0;
    function expandAroundCenter(left, right) {
        let count = 0;
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            count++;
            left--;
            right++;
        }
        return count;
    }
    for (let center = 0; center < s.length; center++) {
        total += expandAroundCenter(center, center);     // Odd length
        total += expandAroundCenter(center, center + 1); // Even length
    }
    return total;
};
      

Time and Space Complexity

• Brute-force approach: For each of the O(n^2) substrings, checking if a substring is a palindrome takes up to O(n) time, so the total time is O(n^3). Space complexity is O(1) unless you store all substrings.
• Expand Around Center approach: There are 2n-1 centers, and for each center, expanding takes up to O(n) time in the worst case. So the total time is O(n^2). Space complexity is O(1) because we only use counters and pointers.

The optimized approach is much faster and suitable for strings up to 1000 characters.

Summary

The key to efficiently counting palindromic substrings is recognizing that every palindrome can be expanded from its center. By iterating through all possible centers (including gaps between characters for even-length palindromes) and expanding outward, we count all palindromic substrings in O(n^2) time and constant space. This approach is both simple and powerful, making it ideal for this problem.