Palindromic Substrings

LeetCode 647: Palindromic Substrings Solution & Explanation

Problem Overview

TL;DR: The optimal solution iterates through every possible center of a palindrome (both single characters and pairs of characters) and expands outward using two pointers to count valid palindromes.

The LeetCode 647 problem, titled Palindromic Substrings, asks us to count the total number of contiguous substrings within a given string s that are palindromes. A palindrome is defined as a sequence that reads the same forwards and backwards.

For example, in the string "aaa", the palindromic substrings are "a", "a", "a" (indices 0, 1, 2), "aa", "aa" (indices 0-1, 1-2), and "aaa" (indices 0-2), resulting in a total of 6.

Brute Force Approach for Palindromic Substrings

The naive approach involves generating every possible substring and verifying if each one is a palindrome.

1. Use nested loops to define the start (i) and end (j) of every substring.
2. For each substring defined by s[i...j], iterate from the ends inward to check if it reads the same forwards and backwards.
3. If it is a palindrome, increment a counter.

Pseudo-code:

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.

Algorithm Strategy: Two Pointers Patterns

The strategy utilizes the Expanding From Center approach to reduce complexity from $O(N^3)$ to $O(N^2)$.

1. Initialize a global counter to zero.
2. Iterate through each index of the string to represent the "center" of a potential palindrome.
3. For each index, perform two expansions:
   • Odd Expansion: Initialize left and right pointers to the current index.
   • Even Expansion: Initialize left to the current index and right to the current index + 1.
4. During each expansion:
   • Check if left and right are within valid bounds ($0 \le left$ and $right < N$).
   • Check if s[left] == s[right].
   • If both conditions are true, we found a palindrome. Increment the global counter.
   • Decrement left and increment right to expand the window.
   • If the condition fails, break the inner loop immediately (a larger string cannot be a palindrome if the core is not).
5. Return the total count.

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.

Pattern Reuse Notes

The Two Pointers - Expanding From Center pattern is a powerful tool for string manipulation problems involving symmetry.

• LeetCode 5: Longest Palindromic Substring: This problem is nearly identical. Instead of incrementing a counter during expansion, you track the maximum length found. The expansion logic remains exactly the same.

Reference Implementation

C++ Solution for LeetCode 647

1class Solution {
2public:
3    int countSubstrings(string s) {
4        int count = 0;
5        int n = s.length();
6        
7        for (int i = 0; i < n; i++) {
8            // Odd length palindromes (single character center)
9            expandAroundCenter(s, i, i, count);
10            
11            // Even length palindromes (two character center)
12            expandAroundCenter(s, i, i + 1, count);
13        }
14        
15        return count;
16    }
17
18private:
19    void expandAroundCenter(const string& s, int left, int right, int& count) {
20        while (left >= 0 && right < s.length() && s[left] == s[right]) {
21            count++;
22            left--;
23            right++;
24        }
25    }
26};

Java Solution for LeetCode 647

1class Solution {
2    public int countSubstrings(String s) {
3        int count = 0;
4        
5        for (int i = 0; i < s.length(); i++) {
6            // Odd length palindromes
7            count += expandAroundCenter(s, i, i);
8            
9            // Even length palindromes
10            count += expandAroundCenter(s, i, i + 1);
11        }
12        
13        return count;
14    }
15    
16    private int expandAroundCenter(String s, int left, int right) {
17        int found = 0;
18        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
19            found++;
20            left--;
21            right++;
22        }
23        return found;
24    }
25}

Python Solution for LeetCode 647

1class Solution:
2    def countSubstrings(self, s: str) -> int:
3        count = 0
4        n = len(s)
5        
6        def expand_around_center(left: int, right: int) -> int:
7            local_count = 0
8            while left >= 0 and right < n and s[left] == s[right]:
9                local_count += 1
10                left -= 1
11                right += 1
12            return local_count
13            
14        for i in range(n):
15            # Odd length palindromes
16            count += expand_around_center(i, i)
17            # Even length palindromes
18            count += expand_around_center(i, i + 1)
19            
20        return count