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)$