Palindromic Substrings

---

Palindromic Substrings: 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.

---

Try this Problem on your own or check similar problems:

1. Longest Palindromic Substring
2. Longest Palindromic Subsequence

Solution:

Java

public int countSubstrings(String s) {
    int n = s.length();
    if(n == 1) return 1;

    boolean[] dp = new boolean[n];
    int count = 0;

    for(int i = n - 1; i >= 0; --i){
        for(int j = n - 1; j >= i; --j){
            if(s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[j-1])){
                dp[j] = true;
                ++count;
            }else{
                dp[j] = false;
            }
        }
    }

    return count;
}

JavaScript

/**
 * @param {string} s
 * @return {number}
 */
var countSubstrings = function (s) {
  const n = s.length;
  if (n === 1) return 1;

  const dp = Array(n).fill(false);
  let count = 0;

  for (let i = n - 1; i >= 0; i--) {
    for (let j = n - 1; j >= i; j--) {
      if (s[i] === s[j] && (j - i <= 2 || dp[j - 1])) {
        dp[j] = true;
        count++;
      } else {
        dp[j] = false;
      }
    }
  }

  return count;
};

Python

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        if n == 1:
            return 1

        dp = [False] * n
        count = 0

        for i in range(n - 1, -1, -1):
            for j in range(n - 1, i - 1, -1):
                if s[i] == s[j] and (j - i <= 2 or dp[j - 1]):
                    dp[j] = True
                    count += 1
                else:
                    dp[j] = False

        return count

C++

class Solution {
public:
    int countSubstrings(string s) {
        const int n = s.length();
        if (n == 1) return 1;

        vector<bool> dp(n, false);
        int count = 0;

        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j >= i; j--) {
                if (s[i] == s[j] && (j - i <= 2 || dp[j - 1])) {
                    dp[j] = true;
                    count++;
                } else {
                    dp[j] = false;
                }
            }
        }

        return count;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(n^2)
• Space Complexity: O(n)

---

Explanation:

The solution is identical to Longest Palindromic Substring but instead keeping track of the maxLength we keep track of count (same optimizations apply for this solution). For the sake of completeness let's investigate one interesting solution to this problem. The main idea is that for each character we expand left and right and check for palindromes of even and odd length, the implementation is trivial:

Java

class Solution {

  int count = 1;
  public int countSubstrings(String s) {
    int n = s.length();
    if(n == 1) return 1;

    for(int i=0; i < n-1; ++i){
        helper(s,i,i);
        helper(s,i,i+1);
    }

    return count;
  }

  private void helper(String s, int i, int j) {
    while(i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)){
      ++count;
      --i;
      ++j;
    }
  }
}

JavaScript

/**
 * @param {string} s
 * @return {number}
 */
let count = 1;
var countSubstrings = function (s) {
  const n = s.length;
  if (n === 1) return 1;

  for (let i = 0; i < n - 1; i++) {
    helper(s, i, i);
    helper(s, i, i + 1);
  }

  return count;
};

function helper(s, i, j) {
  while (i >= 0 && j < s.length && s.charAt(i) === s.charAt(j)) {
    count++;
    i--;
    j++;
  }
}

Python

class Solution:
    count = 1
    def countSubstrings(self, s: str) -> int:
       n = len(s)
        if n == 1:
            return 1

        for i in range(n - 1):
            self.helper(s, i, i)
            self.helper(s, i, i + 1)

        return self.count

    def helper(self, s: str, i: int, j: int) -> None:
        while i >= 0 and j < len(s) and s[i] == s[j]:
            self.count += 1
            i -= 1
            j += 1

C++

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.length();
        if (n == 1) return 1;

        for (int i = 0; i < n - 1; i++) {
            helper(s, i, i);
            helper(s, i, i + 1);
        }

        return count;
    }

private:
    int count = 1;
    void helper(string s, int i, int j) {
        while (i >= 0 && j < s.length() && s[i] == s[j]) {
            count++;
            i--;
            j++;
        }
    }
};