Skip to content

647. 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.

Solution:

class Solution {
    public int countSubstrings(String s) {
        int n = s.length();

        int result = 0;

        boolean[][] dp = new boolean[n][n];

        // dp[i][j]  means from s index i to j whether is parlindromic

        for (int i = 0; i < n; i++){
            dp[i][i] = true;
            result++;
        }

        for (int i = 0; i < n -1; i++){
            if (s.charAt(i) == s.charAt(i+1)){
                dp[i][i+1] = true;
                result++;
            }
        }

        for (int diff = 2; diff < n; diff++){
            for (int i = 0; i < n - diff; i++){
                // i start
                int j = i + diff; // end
                if (s.charAt(i) == s.charAt(j) && dp[i+1][j-1]){
                    dp[i][j] = true;
                    result++;
                }
            }
        }

        return result;
    }
}

// TC: O(n^2)
// SC: O(n^2)

Reference:

https://leetcode.com/problems/palindromic-substrings/

This document is written so well.