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 . This implies an solution is acceptable ( 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 and checking if s[i...j] is a palindrome. Checking the palindrome property takes time, leading to an overall complexity of . Given , this results in roughly 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 per center, resulting in an overall complexity. Since there are character centers and gap centers (between characters), this approach is optimal for counting without using extra space.
Approach
We will use the Center Expansion technique:
- Initialize a counter to zero.
- Iterate through each index
ifrom0ton-1. This index represents the center of an odd-length palindrome (e.g., “aba”). We expandleftandrightstarting ati. - To handle even-length palindromes (e.g., “abba”), we treat the gap between
iandi+1as a center. We expandleftfromiandrightfromi+1. - For each center, use a
whileloop to expand while characters match and indices are within bounds. Increment the counter for every valid expansion. - 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: . We have potential centers (characters + gaps). In the worst case (e.g., “aaaa…”), each center expands times. Total operations .
- Space Complexity: . 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:
nis 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.