Similar Problems

Similar Problems not available

Palindromic Substrings - Leetcode Solution

LeetCode:  Palindromic Substrings Leetcode Solution

Difficulty: Medium

Topics: string dynamic-programming  

Problem Description:

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 substrings: "a", "a", "a", "aa", "aa", "aaa".


The solution to this problem can be achieved using Dynamic Programming. For a string to be palindromic, it should have 1 or 2 characters repeating at the beginning and end of each subproblem. We can use a two-dimensional boolean array to keep track of the subproblems. So, if we have a palindromic substring substring(i, j), then substring(i+1, j-1) should also be a palindromic substring if the characters at position i and j are equal.


  1. Initialize a two-dimensional boolean array dp of size n x n, where n is the length of the string s.
  2. Initialize a count variable to 0.
  3. Traverse the string s from the end and for each index i: a. Traverse the string s from i to the end and for each index j: i. If i and j are equal, set the value of dp[i][j] to True ii. If the value of dp[i][j] is True, increase the count by 1.
  4. Return the count.


public int countSubstrings(String s) { int n = s.length(); boolean[][] dp = new boolean[n][n]; int count = 0;

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

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

Palindromic Substrings Solution Code