LeetCode 647 - Palindromic Substrings

The problem asks us to count how many palindromic substrings exist inside a given string s. A substring is any contiguous segment of the string. This means we cannot rearrange characters or skip positions.

leetcodemediumtwo-pointersstringdynamic-programming

LeetCode Problem 647

Difficulty: 🟡 Medium
Topics: Two Pointers, String, Dynamic Programming

Solution

Problem Understanding

The problem asks us to count how many palindromic substrings exist inside a given string s.

A substring is any contiguous segment of the string. This means we cannot rearrange characters or skip positions. For example, in "abc", "ab" is a substring, but "ac" is not because the characters are not adjacent.

A palindrome is a sequence that reads the same from left to right and right to left. Single characters are always palindromes because reversing them produces the same character. Longer substrings may or may not be palindromes depending on whether their characters mirror around the center.

The input is a single string s, consisting only of lowercase English letters. The output is an integer representing the total number of palindromic substrings in s.

An important detail is that duplicate substrings count separately if they appear at different positions. For example, in "aaa", the substring "a" appears three times, and all three occurrences count independently.

The constraints are:

  • 1 <= s.length <= 1000
  • s contains only lowercase English letters

The maximum length of 1000 tells us that a cubic time solution may become too slow. A quadratic solution is much more appropriate.

There are several important edge cases to consider. A string of length 1 should return 1 because the single character itself is a palindrome. Strings with all distinct characters, such as "abc", only contribute single-character palindromes. Strings with repeated characters, such as "aaa", generate many overlapping palindromes and are often where incorrect implementations fail. Even-length palindromes like "abba" and odd-length palindromes like "aba" must both be handled correctly.

Approaches

Brute Force Approach

A straightforward way to solve this problem is to generate every possible substring and check whether it is a palindrome.

For a string of length n, there are O(n²) possible substrings because each substring is defined by a starting and ending position. For each substring, we can verify whether it is a palindrome by comparing characters from both ends toward the center, which takes O(n) time in the worst case.

This approach is correct because it explicitly examines every substring and counts only those that satisfy the palindrome condition. However, it is inefficient because checking all substrings individually leads to cubic time complexity.

Key Insight for an Optimal Solution

Instead of generating every substring and testing it independently, we can exploit an important property of palindromes:

Every palindrome expands outward from a center.

For example:

  • "aba" expands around the center 'b'
  • "abba" expands around the gap between the two 'b' characters

This observation means that instead of enumerating substrings first, we can start from every possible center and expand outward as long as the characters match.

Since each expansion checks matching characters directly, we avoid redundant palindrome checks and reduce the complexity significantly.

There are two kinds of centers:

  1. Odd-length palindrome centers, where a character itself is the center.
  2. Even-length palindrome centers, where the center lies between two characters.

For a string of length n, there are 2n - 1 possible centers.

Approach Time Complexity Space Complexity Notes
Brute Force O(n³) O(1) Generate every substring and check each palindrome manually
Optimal, Expand Around Center O(n²) O(1) Expand outward from every valid palindrome center

Algorithm Walkthrough

Optimal Algorithm, Expand Around Center

  1. Initialize a counter variable to track the number of palindromic substrings found.
  2. Iterate through every position in the string and treat it as the center of an odd-length palindrome. For example, in "aba", the center is 'b'.
  3. Expand outward from this center using two pointers, left and right. Initially, both pointers point to the same index.
  4. While the pointers stay inside the string and the characters at both positions match, we have found a palindrome. Increment the counter and continue expanding outward.
  5. For the same index, also check an even-length palindrome center. In this case, the center lies between adjacent characters, so initialize left = i and right = i + 1.
  6. Repeat the same expansion process. Whenever characters match, count a palindrome and expand farther outward.
  7. Continue until all possible centers have been processed.
  8. Return the final count.

The reason for checking both odd and even centers is that palindromes can have either form. For example, "aba" has a single-character center, while "abba" has a center between two characters.

Why it works

The algorithm works because every palindrome has a unique center. By iterating through all possible centers and expanding outward, we guarantee that every valid palindrome is counted exactly once. Since expansion only continues when mirrored characters match, every counted substring is guaranteed to be a palindrome.

Python Solution

class Solution:
    def countSubstrings(self, s: str) -> int:
        def expand_from_center(left: int, right: int) -> int:
            palindrome_count = 0

            while left >= 0 and right < len(s) and s[left] == s[right]:
                palindrome_count += 1
                left -= 1
                right += 1

            return palindrome_count

        total_palindromes = 0

        for index in range(len(s)):
            total_palindromes += expand_from_center(index, index)
            total_palindromes += expand_from_center(index, index + 1)

        return total_palindromes

The implementation follows the expand-around-center strategy directly.

A helper function, expand_from_center, handles the palindrome expansion logic. It receives two pointers, left and right, representing the current center. The function keeps expanding outward as long as the pointers remain inside the string and the characters match.

Each successful expansion represents a valid palindrome, so the counter is incremented.

Inside the main loop, we process every index as both an odd-length and even-length center. For odd-length palindromes, both pointers start at the same index. For even-length palindromes, the pointers begin at adjacent positions.

The final answer accumulates all palindromes discovered during expansion.

Go Solution

func countSubstrings(s string) int {
	n := len(s)
	totalPalindromes := 0

	expandFromCenter := func(left, right int) int {
		palindromeCount := 0

		for left >= 0 && right < n && s[left] == s[right] {
			palindromeCount++
			left--
			right++
		}

		return palindromeCount
	}

	for i := 0; i < n; i++ {
		totalPalindromes += expandFromCenter(i, i)
		totalPalindromes += expandFromCenter(i, i+1)
	}

	return totalPalindromes
}

The Go implementation mirrors the Python logic closely. A local function, expandFromCenter, encapsulates the expansion behavior.

One Go-specific consideration is string indexing. Since the problem guarantees lowercase English letters, indexing into the string using byte positions is safe because each character occupies a single byte. If Unicode characters were involved, converting to a rune slice would be necessary.

There are no concerns about integer overflow because the maximum number of palindromic substrings for a string of length 1000 is at most 1000 × 1001 / 2, which comfortably fits inside a Go int.

Worked Examples

Example 1

Input:

s = "abc"

We process each center.

Index Center Type Expansion Palindromes Found Running Total
0 Odd "a" 1 1
0 Even none 0 1
1 Odd "b" 1 2
1 Even none 0 2
2 Odd "c" 1 3
2 Even none 0 3

Final result:

3

The palindromic substrings are:

"a", "b", "c"

Example 2

Input:

s = "aaa"
Index Center Type Expansion Sequence Count Added Running Total
0 Odd "a" 1 1
0 Even "aa" 1 2
1 Odd "a" → "aaa" 2 4
1 Even "aa" 1 5
2 Odd "a" 1 6
2 Even none 0 6

Final result:

6

The palindromic substrings are:

"a", "a", "a", "aa", "aa", "aaa"

Complexity Analysis

Measure Complexity Explanation
Time O(n²) Each center may expand across the string in the worst case
Space O(1) Only a few variables are used, no extra data structures

Although there are 2n - 1 centers, each expansion performs character comparisons directly without storing substrings. In the worst case, such as "aaaaa...", every center expands nearly across the entire string, leading to quadratic time complexity.

The algorithm uses constant extra memory because it only maintains pointer variables and counters.

Test Cases

solution = Solution()

assert solution.countSubstrings("abc") == 3  # basic distinct characters
assert solution.countSubstrings("aaa") == 6  # repeated characters with overlap
assert solution.countSubstrings("a") == 1  # minimum length string
assert solution.countSubstrings("aa") == 3  # even-length palindrome
assert solution.countSubstrings("aba") == 4  # odd-length palindrome
assert solution.countSubstrings("abba") == 6  # even-length nested palindrome
assert solution.countSubstrings("racecar") == 10  # longer odd palindrome
assert solution.countSubstrings("abcd") == 4  # no multi-character palindrome
assert solution.countSubstrings("aaaa") == 10  # maximum overlap behavior
assert solution.countSubstrings("abccba") == 9  # even-length full palindrome
Test Why
"abc" Validates simple distinct characters
"aaa" Tests overlapping palindromes
"a" Verifies minimum input size
"aa" Ensures even-length palindrome handling
"aba" Ensures odd-length palindrome handling
"abba" Verifies nested even-length palindromes
"racecar" Tests larger odd palindrome expansion
"abcd" Confirms only single-character palindromes count
"aaaa" Stresses repeated-character behavior
"abccba" Verifies full-string even palindrome

Edge Cases

Single Character String

A string such as "a" is the smallest valid input. This case can expose bugs if the implementation assumes at least two characters exist for expansion. Our implementation handles this naturally because every index is treated as an odd-length center, producing exactly one palindrome.

All Characters Are Different

A string such as "abcd" contains no multi-character palindromes. A buggy implementation might accidentally overcount or incorrectly treat adjacent characters as palindromes. Here, every expansion beyond length 1 fails immediately because neighboring characters do not match.

Repeated Characters and Overlapping Palindromes

Strings like "aaaa" are especially important because they contain many overlapping palindromes. A naive implementation may miss duplicates or fail to count overlapping regions correctly. The expand-around-center method handles this naturally because each center independently expands outward and counts every valid occurrence.

Even-Length Palindromes

Cases like "abba" can break implementations that only check odd-length centers. Since the palindrome center lies between two characters, odd-center logic alone would miss it. Our implementation explicitly checks both (i, i) and (i, i + 1) centers, guaranteeing even-length palindromes are counted correctly.