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.
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 <= 1000
s
consists of lowercase English letters.
Solutions
Solution 1
| class Solution:
def countSubstrings(self, s: str) -> int:
ans, n = 0, len(s)
for k in range(n * 2 - 1):
i, j = k // 2, (k + 1) // 2
while ~i and j < n and s[i] == s[j]:
ans += 1
i, j = i - 1, j + 1
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | class Solution {
public int countSubstrings(String s) {
int ans = 0;
int n = s.length();
for (int k = 0; k < n * 2 - 1; ++k) {
int i = k / 2, j = (k + 1) / 2;
while (i >= 0 && j < n && s.charAt(i) == s.charAt(j)) {
++ans;
--i;
++j;
}
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | class Solution {
public:
int countSubstrings(string s) {
int ans = 0;
int n = s.size();
for (int k = 0; k < n * 2 - 1; ++k) {
int i = k / 2, j = (k + 1) / 2;
while (~i && j < n && s[i] == s[j]) {
++ans;
--i;
++j;
}
}
return ans;
}
};
|
| func countSubstrings(s string) int {
ans, n := 0, len(s)
for k := 0; k < n*2-1; k++ {
i, j := k/2, (k+1)/2
for i >= 0 && j < n && s[i] == s[j] {
ans++
i, j = i-1, j+1
}
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | /**
* @param {string} s
* @return {number}
*/
var countSubstrings = function (s) {
let ans = 0;
const n = s.length;
for (let k = 0; k < n * 2 - 1; ++k) {
let i = k >> 1;
let j = (k + 1) >> 1;
while (~i && j < n && s[i] == s[j]) {
++ans;
--i;
++j;
}
}
return ans;
};
|
Solution 2