Palindromic Substrings
Given a string, write a function to return the count of all possible palindromic substrings. A palindromic substring is a substring that reads the same backward as forward.
Constraints:
- 1 <= s.length <= 1000
- s consists of lowercase English letters.
Examples:
Input: "abc"
Output: 3
Explanation: Three palindromic substrings: "a", "b", "c".
Input: "aaa"
Output: 6
Explanation: Six palindromic substrings: "a", "a", "a", "aa", "aa", "aaa".
Solutions
Expand Around Center
Time: O(n^2)Space: O(1)
The approach is to expand around the center of the palindrome. We consider each character as the center of a potential palindrome and expand outwards to count the number of palindromic substrings. We also consider the case where the center of the palindrome is between two characters.
function countSubstrings(s) {
let count = 0;
for (let i = 0; i < s.length; i++) {
count += countPalindromes(s, i, i);
count += countPalindromes(s, i, i + 1);
}
return count;
}
function countPalindromes(s, left, right) {
let count = 0;
while (left >= 0 && right < s.length && s[left] === s[right]) {
count++;
left--;
right++;
}
return count;
}
Follow-up:
How would you optimize the solution to handle very large strings?
