Palindromic Substrings
You're given a string s. Return how many of its substrings are palindromes, meaning they read the same forward and backward. A substring is a contiguous, non-empty run of characters, and substrings at different positions count separately even when their text is the same.
Examples
s = "abba" returns 6
The four single letters, plus "bb" and "abba".
s = "xyz" returns 3
No two neighboring letters match, so only the single letters count.
s = "aaaa" returns 10
Every substring is a palindrome: four of length 1, three of length 2, two of length 3, and one of length 4.
Constraints
- 1 <= s.length <= 1000
- s consists of lowercase English letters.
Hints
A palindrome stays a palindrome when you peel off its first and last characters. What does that suggest about growing palindromes instead?
Expand around each possible center. Remember that even-length palindromes are centered between two characters.
For each i, expand from (i, i) and from (i, i + 1): while both indices are in range and s[l] == s[r], count one, then move l left and r right.
Drill This: Your Approach First
Approach
Every palindrome has a center: a single character for odd lengths, or the gap between two characters for even lengths. A string of length n has 2n - 1 centers. From each center, expand outward while the characters on both sides match, counting one palindrome per successful step. This is the same recurrence as the dynamic programming table, where s[i..j] is a palindrome when s[i] == s[j] and s[i+1..j-1] is one, walked outward from each center so it needs no table. O(n^2) time, O(1) space.
Time
O(n^2)
Space
O(1)
Pitfall
Solutions
class Solution {
public int countSubstrings(String s) {
int count = 0;
for (int i = 0; i < s.length(); i++) {
count += expand(s, i, i);
count += expand(s, i, i + 1);
}
return count;
}
private int expand(String s, int l, int r) {
int found = 0;
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
found++;
l--;
r++;
}
return found;
}
}class Solution:
def countSubstrings(self, s: str) -> int:
def expand(l: int, r: int) -> int:
found = 0
while l >= 0 and r < len(s) and s[l] == s[r]:
found += 1
l -= 1
r += 1
return found
return sum(expand(i, i) + expand(i, i + 1) for i in range(len(s)))