25 ms Java DP. Space - O(n^2)

  • 1

    Here is a DP solution. dp[i][j] is true is the substring from index i to index j is a palindrome. Each time I encounter a palindrome, I increment the count.
    dp[i][j] will depend upon the the ith character matching the jth character and whether the substring from i+1 to j-1 is a palindrome or not.

    public class Solution {
    public int countSubstrings(String s) {

        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        int count = 0;
        for(int i = 0; i < len; i++)
            Arrays.fill(dp[i], true);
        for(int i = len - 1; i >= 0; i--){
            for(int j = i; j < len; j++){
                if(i == j){
                dp[i][j] = (s.charAt(i) == s.charAt(j)) && dp[i+1][j-1];
        return count;


Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.