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.
public
class Solution {
public int countSubstrings(String s) {
int count = 0;
for (int i = 0;
i < s.length();
i++) {
count += countPalindromes(s, i, i);
count += countPalindromes(s, i, i + 1);
}
return count;
}
private int countPalindromes(String s, int left, int right) {
int count = 0;
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
count++;
left--;
right++;
}
return count;
}
}Follow-up:
How would you optimize the solution to handle very large strings?
