Palindromic Substrings - Leetcode Solution

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

Approach:

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.

Algorithm:

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.

Code:

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;
                else
                    dp[i][j] = dp[i+1][j-1];
            }
            if(dp[i][j])
                count++;
        }
    }
    return count;
}

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

1