Problem Description

You are given a string s. Your task is to count how many palindromic substrings exist within this string.

A palindrome is a string that reads the same forwards and backwards. For example, "aba", "racecar", and "a" are palindromes.

A substring is any contiguous sequence of characters taken from the original string. For instance, if s = "abc", then the substrings are: "a", "b", "c", "ab", "bc", and "abc".

The solution uses an expand-around-center approach. It iterates through 2n - 1 possible centers (where n is the length of the string). Why 2n - 1? Because palindromes can have either odd length (centered at a single character) or even length (centered between two characters).

For each center position k:

• When k is even, it represents a center at character index k // 2 (odd-length palindromes)
• When k is odd, it represents a center between characters at indices k // 2 and (k + 1) // 2 (even-length palindromes)

The algorithm expands outward from each center using two pointers i and j. As long as the characters at positions i and j match and stay within bounds, it counts this as a valid palindrome and continues expanding by moving i left and j right.

The ~i condition checks if i >= 0 (since ~i is false when i is -1), and j < n ensures we don't go past the string's end. Each valid expansion represents a palindromic substring, so the counter is incremented accordingly.

Intuition

The key insight is that every palindrome has a center. If we can identify all possible centers in a string and expand outward from each center, we can find all palindromic substrings.

Consider how palindromes are structured:

• Odd-length palindromes like "aba" have a single character as their center
• Even-length palindromes like "abba" have their center between two characters

This means for a string of length n, we have:

• n possible centers for odd-length palindromes (at each character)
• n - 1 possible centers for even-length palindromes (between each pair of adjacent characters)
• Total: 2n - 1 possible centers

Instead of checking every possible substring to see if it's a palindrome (which would be inefficient), we can be smarter. Starting from each potential center, we expand outward symmetrically. As long as the characters on both sides match, we have found a valid palindrome.

The beauty of this approach is that once characters don't match, we can stop expanding from that center immediately. This is because if the outer characters don't match, adding more characters even further out won't create a palindrome either.

By using a single loop that handles both odd and even-length palindromes through clever index calculation (i = k // 2 and j = (k + 1) // 2), we avoid code duplication. When k is even, i and j start at the same position (odd-length center). When k is odd, they start at adjacent positions (even-length center).

This expand-around-center technique efficiently finds all palindromic substrings in O(n²) time, which is optimal for this problem since there can be up to O(n²) palindromic substrings in the worst case.

Learn more about Two Pointers and Dynamic Programming patterns.

Solution Approach

The implementation uses the expand-around-center technique with a single loop to handle both odd and even-length palindromes.

Step-by-step walkthrough:

1. Initialize variables: Set ans = 0 to count palindromes and get the string length n.

2. Iterate through all possible centers: Loop through k from 0 to 2n - 2 (total of 2n - 1 iterations).

3. Calculate starting positions for expansion:

   • i = k // 2 - left pointer starting position
   • j = (k + 1) // 2 - right pointer starting position

   When k is even (0, 2, 4...):

   • Both i and j point to the same index (e.g., when k = 0: i = 0, j = 0)
   • This handles odd-length palindromes centered at a single character

   When k is odd (1, 3, 5...):

   • i and j point to adjacent indices (e.g., when k = 1: i = 0, j = 1)
   • This handles even-length palindromes centered between two characters

4. Expand around the center:

   • The while loop condition ~i and j < n and s[i] == s[j] checks:
     • ~i: Ensures i >= 0 (bitwise NOT of -1 gives 0, which is falsy)
     • j < n: Ensures we don't exceed the string boundary
     • s[i] == s[j]: Characters match, forming a palindrome

5. Count and continue expanding:

   • When all conditions are met, increment ans by 1
   • Expand outward: i -= 1 and j += 1
   • Continue until characters don't match or boundaries are reached

6. Return the total count of palindromic substrings.

Example trace for s = "aaa":

• k = 0: Start at (0,0), expand to find "a"
• k = 1: Start at (0,1), expand to find "aa"
• k = 2: Start at (1,1), expand to find "a", "aaa"
• k = 3: Start at (1,2), expand to find "aa"
• k = 4: Start at (2,2), expand to find "a"
• Total: 6 palindromic substrings

The algorithm efficiently explores all possible palindromes with O(n²) time complexity and O(1) space complexity.

Example Walkthrough

Let's trace through the algorithm with s = "aba":

String visualization:

Index: 0 1 2
Char:  a b a

We'll iterate through 2n - 1 = 5 possible centers (k = 0 to 4):

k = 0 (odd-length center at index 0):

• i = 0 // 2 = 0, j = 1 // 2 = 0
• Start at position (0, 0): s[0] = 'a', s[0] = 'a' ✓ Match
• Count palindrome "a", ans = 1
• Expand: i = -1, j = 1
• Stop (i < 0)

k = 1 (even-length center between indices 0 and 1):

• i = 1 // 2 = 0, j = 2 // 2 = 1
• Start at position (0, 1): s[0] = 'a', s[1] = 'b' ✗ No match
• Stop immediately

k = 2 (odd-length center at index 1):

• i = 2 // 2 = 1, j = 3 // 2 = 1
• Start at position (1, 1): s[1] = 'b', s[1] = 'b' ✓ Match
• Count palindrome "b", ans = 2
• Expand: i = 0, j = 2
• Check position (0, 2): s[0] = 'a', s[2] = 'a' ✓ Match
• Count palindrome "aba", ans = 3
• Expand: i = -1, j = 3
• Stop (i < 0)

k = 3 (even-length center between indices 1 and 2):

• i = 3 // 2 = 1, j = 4 // 2 = 2
• Start at position (1, 2): s[1] = 'b', s[2] = 'a' ✗ No match
• Stop immediately

k = 4 (odd-length center at index 2):

• i = 4 // 2 = 2, j = 5 // 2 = 2
• Start at position (2, 2): s[2] = 'a', s[2] = 'a' ✓ Match
• Count palindrome "a", ans = 4
• Expand: i = 1, j = 3
• Stop (j >= n)

Final answer: 4 palindromic substrings ("a", "b", "aba", "a")

Solution Implementation

Time and Space Complexity

Time Complexity: O(n²)

The algorithm iterates through 2n - 1 possible centers for palindromes (n single-character centers and n-1 between-character centers). For each center position k, it expands outward using two pointers i and j. In the worst case, when the entire string is the same character (e.g., "aaaa"), each expansion can extend to the boundaries of the string, taking O(n) time. Therefore, the overall time complexity is O(n) * O(n) = O(n²).

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space. The variables ans, n, k, i, and j are the only additional storage used, regardless of the input size. No additional data structures like arrays or recursion stacks are employed, making the space complexity constant.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Confusing the center indexing logic

Many developers struggle to understand why we need 2n - 1 centers and how the index calculation works. A common mistake is trying to handle odd and even-length palindromes in separate loops, which leads to more complex and error-prone code:

Incorrect approach:

# Separate loops for odd and even palindromes
count = 0
# Check odd-length palindromes
for i in range(len(s)):
    left, right = i, i
    while left >= 0 and right < len(s) and s[left] == s[right]:
        count += 1
        left -= 1
        right += 1

# Check even-length palindromes
for i in range(len(s) - 1):
    left, right = i, i + 1
    while left >= 0 and right < len(s) and s[left] == s[right]:
        count += 1
        left -= 1
        right += 1

Solution: Use the unified approach with k // 2 and (k + 1) // 2 to handle both cases in a single loop. This reduces code duplication and potential for errors.

2. Off-by-one errors in the loop range

A frequent mistake is using range(2 * n) instead of range(2 * n - 1), which would cause an index out of bounds error when accessing the string.

Incorrect:

for center in range(2 * n):  # Wrong! Goes up to 2n-1, but we only have 2n-1 centers
    left = center // 2
    right = (center + 1) // 2  # When center = 2n-1, right = n, causing index error

Solution: Always use range(2 * n - 1) to iterate through exactly 2n - 1 centers.

3. Forgetting to count single characters as palindromes

Some implementations mistakenly skip counting single characters or start expanding without counting the initial center position:

Incorrect:

while left >= 0 and right < n and s[left] == s[right]:
    left -= 1
    right += 1
    count += 1  # Counting AFTER expansion misses the center itself

Solution: Count the palindrome BEFORE expanding (increment count first, then move pointers).

4. Using complex boundary checks

The ~i notation might be confusing. Some developers try to "simplify" it but end up with incorrect logic:

Incorrect attempts:

# Wrong: This would stop at i = 0
while i > 0 and j < n and s[i] == s[j]:

# Overly complex:
while i != -1 and j != len(s) and s[i] == s[j]:

Solution: Use the clear and standard check left >= 0 and right < n. The ~i trick works but can reduce code readability.

5. Not handling edge cases

Failing to consider edge cases like empty strings or single-character strings:

Potential issue:

if not s:  # Unnecessary check that adds complexity
    return 0
if len(s) == 1:  # Also unnecessary
    return 1

Solution: The expand-around-center algorithm naturally handles all edge cases:

• Empty string: range(2 * 0 - 1) produces no iterations, returns 0
• Single character: Correctly counts 1 palindrome
• All same characters: Correctly counts all possible palindromic substrings