647. Palindromic Substrings
1. Description
Given a string s, return the number of palindromic substrings in it.
A string is a palindrome when it reads the same backward as forward.
A substring is a contiguous sequence of characters within the string.
2. Example
Example 1:
Input: s = “abc”
Output: 3
Explanation: Three palindromic strings: “a”, “b”, “c”.
Example 2:
Input: s = “aaa”
Output: 6
Explanation: Six palindromic strings: “a”, “a”, “a”, “aa”, “aa”, “aaa”.
3. Constraints
- 1 <= s.length <= 1000
- s consists of lowercase English letters.
4. Solutions
Brute Force
n = str.size()
Time complexity: O($n^2$)
Space complexity: O(1)
Manacher
n = str.size()
Time complexity: O(n)
Space complexity: O(n)
class Solution {
public:
int countSubstrings(string str) {
string extend_str(str.size() * 2 + 3, '#');
extend_str[0] = '@';
extend_str[str.size() * 2 + 2] = '$';
for (int i = 0, j = 2; i < str.size(); ++i, j += 2) {
extend_str[j] = str[i];
}
auto radius = vector<int>(extend_str.size());
int result = 0;
for (int i = 2, max_palin_center = 0, max_known_right = 0; i < extend_str.size() - 1; ++i) {
radius[i] = (i <= max_known_right)
? min(max_known_right - i + 1, radius[2 * max_palin_center - i])
: 1;
while (extend_str[i + radius[i]] == extend_str[i - radius[i]]) {
++radius[i];
}
if (i + radius[i] - 1 > max_known_right) {
max_palin_center = i;
max_known_right = i + radius[i] - 1;
}
result += (radius[i] / 2);
}
return result;
}
};