DP-11. Palindromic Substrings

Problem

LeetCode #647. Palindromic Substrings

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.

Example 1:

Input: "abc"
Output: 3
Explanation: Three palindromic strings: “a”, “b”, “c”.
Example 2:

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

Explanation

This problme is quite similar to Longest Palindromic Substring. The pattern is almost the same. The only difference is this time, we do not compare the length, we just add the count.

Solution

Time complexity is O(n^2)
Space complexity is O(n^2), it uses O(n^2) space to save the table.

dp[i][j] means substring from i to j (inclusive) is a palindrome.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int countSubstrings(String s) {
if (s == null || s.length() == 0) return 0;
int len = s.length();
int res = 0;
boolean[][] dp = new boolean[len][len];

for (int i = len - 1; i >= 0; i--) {
for (int j = i; j < len; j++) {
dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1]);
if (dp[i][j]) res++;
}
}
return res;
}
}