#647
Palindromic Substrings
Medium Expand around centre
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Count how many substrings (by position) are palindromes.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: how many substrings (by position) are palindromes?
Why this works: expand around every centre; each successful step is one more palindrome.
Example: "aaa"
single letters: 3"aa" twice: 2"aaa": 1 → 6
✦Hints open one at a time
Same centres as Longest Palindromic Substring.
Every successful expansion step is one more palindrome.
↗Approach
For each of the 2n − 1 centres, expand while the ends match, adding one to the count each time.
</>Solution (Java)
class Solution {
public int countSubstrings(String s) {
int count = 0;
for (int c = 0; c < 2 * s.length() - 1; c++) {
int l = c / 2, r = l + c % 2; // even c: char centre, odd c: gap centre
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
count++;
l--;
r++;
}
}
return count;
}
}!Common mistake
Generating every substring and checking it — O(n³).
Complexity
- Time: O(n²).
- Space: O(1).
Topic: Strings
🎬 Episodes 16–20: video coming soon