Difficulty: Medium1-D Dynamic Programming

Palindromic Substrings

Problem in Plain English

A substring reads the same forward and backward when its outer characters match all the way inward. Count every contiguous slice of the input string that has this property.

Problem Statement

Given a string s, return the number of palindromic substrings in it. A string is a palindrome when it reads the same backward as forward, and a substring is a contiguous block of characters inside s.

Every single character counts as a palindrome of length 1, and overlapping substrings at different positions are counted separately even when they look identical.

Return the total count across all start and end positions.

Constraints

1 <= s.length <= 1000
s consists of lowercase English letters.

Examples

Example 1

Input: s = "abc"
Output: 3

The three single characters at indices 0, 1, and 2 are palindromes. The other candidates ab, bc, and abc have unequal outer letters, so the count is 3.

Example 2

Input: s = "aaa"
Output: 6

There are three occurrences of a, two occurrences of aa, and one occurrence of aaa. They overlap and repeat the same text, but each start/end pair counts separately: 3 + 2 + 1 = 6.

Example 3

Input: s = "z"
Output: 1

The only non-empty substring is z itself. Its odd center adds one, and the gap after it is already outside the string.

Example 4

Input: s = "abba"
Output: 6

Four single-character occurrences count, plus bb at indices 1..2 and abba at 0..3. Both longer palindromes share the middle gap, showing why even centers and every successful expansion must be counted.

Intuition

Count occurrences, not distinct text: the three one-letter substrings in aaa count separately because their positions differ. A palindrome mirrors around a character for odd lengths or around a gap for even lengths. In Example 1, abc contributes only its three character centers; every neighboring gap fails immediately. Enumerating all endpoint pairs works, but growing each center shares the inner palindrome instead of repeatedly checking it.

Approaches

Brute Force Check

Solution Details

Reveal Brute Force Check: intuition, complexity, and code

Intuition

Enumerate each substring by its start and end indices, then compare symmetric characters inward to decide whether to count it. Working on the original string avoids allocating candidate slices. This direct approach is easy to justify but repeats comparisons for many overlapping substrings.

Step-by-Step Logic

Initialize res = 0. For each start index i, iterate every end index j from i through the final index. Example 1 visits six endpoint pairs for abc.
For each candidate, place left and right at its endpoints. While left is before right, reject on unequal characters; otherwise advance left and retreat right. Reaching the middle accepts the candidate without creating a substring.
Increment the total once for an accepted candidate. Example 1 accepts a, rejects ab and abc, accepts b, rejects bc, and accepts c.
Return the total after all pairs. Example 1 finishes with res = 3.

Why It Works

Every non-empty contiguous substring has exactly one pair of indices i and j with i <= j, and the nested loops visit every such pair exactly once. During the inward check, all pairs outside the current pointers have already matched. A mismatch proves the candidate is not a palindrome; meeting or crossing proves every symmetric pair matched, including the vacuous case of one character. Incrementing only for accepted candidates therefore counts exactly the palindrome occurrences, even when their text is identical.

Dry Run

Brute Force Check: variable states at each step
i	j	candidate (for display only)	left / right check and exit	accepted	res before -> after
0	0	a	(0,0): already met	yes	0 -> 1
0	1	ab	(0,1): a != b; stop	no	1 -> 1
0	2	abc	(0,2): a != c; stop	no	1 -> 1
1	1	b	(1,1): already met	yes	1 -> 2
1	2	bc	(1,2): b != c; stop	no	2 -> 2
2	2	c	(2,2): already met	yes	2 -> 3
return	—	—	all six candidates checked	—	3

Complexity Analysis

Time Complexity

O(n^3)

Space Complexity

O(1)

Let n be the string length. There are n(n + 1)/2 candidate intervals; each check compares at most O(n) character pairs. An all-equal string forces cubic total comparisons. The code uses indices rather than substring copies, so live auxiliary space is O(1), including the nonrecursive helper call and its counters. The scalar result also occupies constant space. At n = 1000 the largest count is 500500, within Java int and exactly representable in JavaScript; no input mutation occurs.

Code

Solution.java

1class Solution {2    public int countSubstrings(String s) {3        int res = 0;4        for (int i = 0; i < s.length(); i++) {5            for (int j = i; j < s.length(); j++) {6                if (isPalindrome(s, i, j)) {7                    res++;8                }9            }10        }11        return res;12    }13
14    private boolean isPalindrome(String s, int left, int right) {15        // Only the unresolved inner pairs remain; endpoints avoid slicing.16        while (left < right) {17            if (s.charAt(left) != s.charAt(right)) return false;18            left++;19            right--;20        }21        return true;22    }23}

Hints

Hint 1

A palindrome has a unique middle: a character for odd lengths, or a gap for even lengths.

Hint 2

For one middle, count every successful outward layer rather than only the widest palindrome.

Hint 3

Expand from both (i, i) and (i, i + 1) at every index. Count while bounds hold and characters match; stop at the first failure.

Edge Cases

A single character like z contributes exactly one odd palindrome and no even palindrome.
For all identical letters, every interval qualifies: the count is $n(n+1)/2$ , or 500500 at the length limit 1000.
All distinct letters like abc contribute exactly n single-character occurrences.
An even middle like the gap in abba can contribute multiple palindromes (bb and abba); counting only character centers misses both.
A mismatch after a successful inner palindrome stops that center, but other centers must still be processed.

Common Mistakes and Interview Tips

Deduplicating by substring text: aaa contains six occurrences, even though there are only three distinct palindrome texts.
Expanding only around characters misses every even-length palindrome, such as bb in abba.
Incrementing once per center instead of once per successful layer misses nested palindromes around the same middle.
Indexing before checking bounds is especially dangerous in Python, where a negative index wraps to the end instead of raising immediately.
Slicing or reversing every candidate changes the allocation behavior; use endpoint indices if claiming constant auxiliary space.
Interview tip: justify completeness using a unique center and radius, and distinguish this count from finding only the longest palindrome.

Key Takeaway

When each valid interval has a unique center, enumerate centers and grow by one layer at a time. A preserved inner invariant replaces repeated full checks; counting every successful radius counts occurrences, while retaining only the largest radius solves a different objective.