Reference: LeetCode
Difficulty: Medium

Problem

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Note: The input string length won’t exceed 1000.

Example:

1
2
3
4
5
6
7
Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Analysis

Brute-Force

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int countSubstrings(String s) {
// Assume s is not null
int n = s.length();
int count = 0;
for (int i = 0; i < n; ++i) {
for (int j = i; j < n; ++j) {
// check if substring [i, j] is palindromic
if (isPalindromic(s, i, j)) ++count;
}
}
return count;
}

private boolean isPalindromic(String s, int lo, int hi) {
int n = hi - lo + 1;
for (int i = 0; i < n / 2; ++i) {
if (s.charAt(lo + i) != s.charAt(hi - i)) return false;
}
return true;
}

Time: $O(N^3)$
Space: $O(1)$

Expansion From the Center

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int countSubstrings(String s) {
// Assume s is not null
int n = s.length();
int count = 0;
for (int i = 0; i < n; ++i) {
count += countPalindrome(s, i, i); // odd length
count += countPalindrome(s, i, i + 1); // even length
}
return count;
}

private int countPalindrome(String s, int lo, int hi) {
int n = s.length();
int count = 0;
while (lo >= 0 && hi < n && s.charAt(lo) == s.charAt(hi)) {
++count;
--lo;
++hi;
}
return count;
}

Time: $O(N^2)$
Space: $O(1)$

DP (marked)

Based on the idea in 5. Longest Palindrome Substring we can use dynamic programming to solve this problem.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public int countSubstrings(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int n = s.length();
boolean[][] dp = generateDP(s);
// Check each substring
int count = 0;
for (int i = 0; i < n; ++i) {
for (int j = i; j < n; ++j) {
if (dp[i][j] == true) ++count;
}
}
return count;
}

private boolean[][] generateDP(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
// Init
for (int i = 0; i < n; ++i) { // diagonal
dp[i][i] = true;
}
for (int i = 0; i < n - 1; ++i) { // one line below diagonal
dp[i][i + 1] = (s.charAt(i) == s.charAt(i + 1));
}
// DP
for (int i = n - 3; i >= 0; --i) {
for (int j = i + 2; j < n; ++j) {
dp[i][j] = dp[i + 1][j - 1] && s.charAt(i) == s.charAt(j);
}
}
return dp;
}

Time: $O(N^2)$
Space: $O(N^2)$


Comment