text
count = 0
for i from 0 to length - 1:
    for j from i to length - 1:
        if isPalindrome(s, i, j):
            count++
return count

Complexity Analysis:

• Time Complexity: $O(N^3)$. There are $O(N^2)$ substrings. Verifying each substring takes $O(N)$ time.
• Why it fails: While the constraint $N \le 1000$ might allow an $O(N^3)$ solution to pass in highly optimized languages (like C++), it performs approximately $10^9$ operations in the worst case. This is inefficient and risks a Time Limit Exceeded (TLE) error on stricter platforms or larger datasets. It is not considered an optimal solution for interviews.

Core Insight for Palindromic Substrings

The intuition behind the optimal LeetCode 647 solution lies in the structure of a palindrome. Every palindrome mirrors around a central point.

If we know that a substring s[i...j] is a palindrome, we can determine if s[i-1...j+1] is a palindrome simply by checking if s[i-1] == s[j+1]. This suggests we should process the string from the inside out.

However, a palindrome can have two types of centers:

1. Odd length: The center is a specific character (e.g., "aba" centers on 'b').
2. Even length: The center is between two characters (e.g., "abba" centers between the two 'b's).

For a string of length $N$, there are $N$ single-character centers and $N-1$ two-character centers, totaling $2N-1$ centers. By placing two pointers at a center and moving them in opposite directions, we can count all palindromes originating from that center in linear time relative to the palindrome's length.

Visual Description: Imagine the string laid out horizontally. For every index $i$, we initiate two expansion processes.

1. Odd Case: Left pointer starts at $i$, Right pointer starts at $i$. We check equality, increment the count, move Left to $i-1$ and Right to $i+1$, and repeat until characters mismatch or bounds are reached.
2. Even Case: Left pointer starts at $i$, Right pointer starts at $i+1$. We perform the same expansion logic.

Execution Flow

Let's trace the algorithm with s = "abc".

1. Initialization: count = 0, n = 3.
2. Loop i = 0 ('a'):
   • Odd Expansion (center 'a'): left=0, right=0. s[0] == s[0]. Valid. count becomes 1. Expand: left=-1, right=1. Out of bounds. Stop.
   • Even Expansion (center 'a', 'b'): left=0, right=1. s[0] != s[1] ('a' != 'b'). Stop.
3. Loop i = 1 ('b'):
   • Odd Expansion (center 'b'): left=1, right=1. s[1] == s[1]. Valid. count becomes 2. Expand: left=0, right=2. s[0] != s[2] ('a' != 'c'). Stop.
   • Even Expansion (center 'b', 'c'): left=1, right=2. s[1] != s[2] ('b' != 'c'). Stop.
4. Loop i = 2 ('c'):
   • Odd Expansion (center 'c'): left=2, right=2. s[2] == s[2]. Valid. count becomes 3. Expand: left=1, right=3. Out of bounds. Stop.
   • Even Expansion (center 'c', null): left=2, right=3. Out of bounds. Stop.
5. Result: Return 3.

Proof of Correctness

The algorithm is correct because every palindromic substring has a unique center. By iterating through all possible $2N-1$ centers (indices for odd length, gaps between indices for even length) and expanding maximally, we are guaranteed to visit every palindromic substring exactly once. The expansion logic strictly adheres to the definition of a palindrome: if the characters at the current boundaries match, the substring is a palindrome; if they do not, no further expansion can yield a palindrome.

Reference Implementation

C++ Solution for LeetCode 647

cpp
class Solution {
public:
    int countSubstrings(string s) {
        int count = 0;
        int n = s.length();
        
        for (int i = 0; i < n; i++) {
            // Odd length palindromes (single character center)
            expandAroundCenter(s, i, i, count);
            
            // Even length palindromes (two character center)
            expandAroundCenter(s, i, i + 1, count);
        }
        
        return count;
    }

private:
    void expandAroundCenter(const string& s, int left, int right, int& count) {
        while (left >= 0 && right < s.length() && s[left] == s[right]) {
            count++;
            left--;
            right++;
        }
    }
};

Java Solution for LeetCode 647

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

Python Solution for LeetCode 647

python
class Solution:
    def countSubstrings(self, s: str) -> int:
        count = 0
        n = len(s)
        
        def expand_around_center(left: int, right: int) -> int:
            local_count = 0
            while left >= 0 and right < n and s[left] == s[right]:
                local_count += 1
                left -= 1
                right += 1
            return local_count
            
        for i in range(n):
            # Odd length palindromes
            count += expand_around_center(i, i)
            # Even length palindromes
            count += expand_around_center(i, i + 1)
            
        return count