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.
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".
Constraints:
1 <= s.length <= 1000sconsists of lowercase English letters.
Companies:
Facebook, Microsoft, Salesforce, Docusign, Amazon
Related Topics:
String, Dynamic Programming
Similar Questions:
// OJ: https://leetcode.com/problems/palindromic-substrings/
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(1)
class Solution {
public:
int countSubstrings(string s) {
int N = s.size(), ans = N; // initially all the single characters are counted
for (int i = 0; i < N; ++i) { // odd length
for (int j = 1; i - j >= 0 && i + j < N && s[i - j] == s[i + j]; ++j) ++ans;
}
for (int i = 1; i < N; ++i) { // even length
for (int j = 0; i - j - 1 >= 0 && i + j < N && s[i - j - 1] == s[i + j]; ++j) ++ans;
}
return ans;
}
};// OJ: https://leetcode.com/problems/palindromic-substrings/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
int countSubstrings(string s) {
string t = "^*";
for (char c : s) {
t += c;
t += '*';
}
t += '$';
int N = s.size(), M = t.size();
vector<int> r(M);
r[1] = 1;
int j = 1, ans = 0;
for (int i = 2; i <= 2 * N; ++i) {
int cur = j + r[j] > i ? min(r[2 * j - i], j + r[j] - i) : 1;
while (t[i - cur] == t[i + cur]) ++cur;
if (i + cur > j + r[j]) j = i;
r[i] = cur;
ans += r[i] / 2;
}
return ans;
}
};