Domain 2MediumCORE

Palindromic Substrings

We are given a string s and need to return the total count of palindromic substrings within it. A substring is defined as a contiguous sequence of characters. Crucially, even if two substrings have identical content (e.g., the 'a' at index 0 and the 'a' at index 2 in 'aba'), they are counted separately because their start/end indices differ.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#String#Dynamic Programming

647. Palindromic Substrings

Model: qwen3.5:9b
Topics: String,Dynamic Programming
FAANG asked: 1
Acceptance rate: 62.7%


Problem Breakdown

We are given a string s and need to return the total count of palindromic substrings within it. A substring is defined as a contiguous sequence of characters. Crucially, even if two substrings have identical content (e.g., the ‘a’ at index 0 and the ‘a’ at index 2 in “aba”), they are counted separately because their start/end indices differ.

Inputs: A string s containing lowercase English letters (based on standard LeetCode constraints, though not explicitly restricted here). Outputs: An integer representing the total count of palindromic substrings. Constraints: Length of s ≤1000\le 1000. This implies an O(N2)O(N^2) solution is acceptable (10610^6 operations), but we should aim for efficiency. Edge Cases:

  • Empty string (length 0).
  • Single character string.
  • Strings with all identical characters (e.g., “aaa”).

Intuition

Initially, a candidate might consider iterating through every possible substring pair (i,j)(i, j) and checking if s[i...j] is a palindrome. Checking the palindrome property takes O(N)O(N) time, leading to an overall complexity of O(N3)O(N^3). Given N=1000N=1000, this results in roughly 10910^9 operations, which risks Time Limit Exceeded (TLE).

The key insight is that every palindrome has a specific “center.” A palindrome expands symmetrically outward from this center. Instead of checking every substring independently, we can iterate through every possible center position and expand outwards as long as the characters match. This reduces the check to O(N)O(N) per center, resulting in an overall O(N2)O(N^2) complexity. Since there are NN character centers and N−1N-1 gap centers (between characters), this approach is optimal for counting without using extra space.

Approach

We will use the Center Expansion technique:

  1. Initialize a counter to zero.
  2. Iterate through each index i from 0 to n-1. This index represents the center of an odd-length palindrome (e.g., “aba”). We expand left and right starting at i.
  3. To handle even-length palindromes (e.g., “abba”), we treat the gap between i and i+1 as a center. We expand left from i and right from i+1.
  4. For each center, use a while loop to expand while characters match and indices are within bounds. Increment the counter for every valid expansion.
  5. Return the final count.

This approach naturally handles both odd and even length palindromes in a single pass over the string centers.

Complexity Analysis

  • Time Complexity: O(N2)O(N^2). We have 2N−12N - 1 potential centers (characters + gaps). In the worst case (e.g., “aaaa…”), each center expands O(N)O(N) times. Total operations ≈N×N\approx N \times N.
  • Space Complexity: O(1)O(1). We only use a few integer variables for indices and the counter, regardless of input size.

Solution

def countSubstrings(s: str) -> int:
    n = len(s)
    count = 0
    
    # Iterate through each character as a center
    for i in range(n):
        # Case 1: Odd length palindromes (centered at character i)
        left, right = i, i
        while left >= 0 and right < n and s[left] == s[right]:
            count += 1
            left -= 1
            right += 1
            
        # Case 2: Even length palindromes (centered between i and i+1)
        left, right = i, i + 1
        while left >= 0 and right < n and s[left] == s[right]:
            count += 1
            left -= 1
            right += 1
            
    return count

Edge Cases Handled

  • Empty String: n is 0, the loop does not execute, returns 0. Correct.
  • Single Character: Loop runs once for odd center (expands 1 step), even center fails immediately. Returns 1. Correct.
  • All Identical Characters (“aaa”): Odd centers expand fully, even centers expand fully. Counts all substrings correctly.