Palindromic Substrings
Count all palindromic substrings. Equal text at different positions counts separately.
Work through the cases
3 examplesInput notation
One nonempty string.Expected result
The number of palindromic substrings.Case 1
Input
aaa
Expected output
6
Case 2
Input
abc
Expected output
3
Case 3
Input
a
Expected output
1
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
Count palindromic substrings. A full n^2 DP table works but is unnecessary if we only need the count. Expand around 2n-1 centers (odd and even) and increment once for every successful step.
We can enumerate the center position of each palindrome and expand outward to count the number of palindromic substrings. For a string of length n, there are 2n-1 possible center positions (covering both odd-length and even-length palindromes). For each center, we expand outward until the palindrome condition is no longer satisfied, and count the number of palindromic substrings.
The time complexity is O(n^2), where n is the length of string s. The space complexity is O(1).
class Solution {
public int countSubstrings(String s) {
int ans = 0;
int n = s.length();
for (int k = 0; k < n * 2 - 1; ++k) {
int i = k / 2, j = (k + 1) / 2;
while (i >= 0 && j < n && s.charAt(i) == s.charAt(j)) {
++ans;
--i;
++j;
}
}
return ans;
}
}Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.