Solution For Palindromic Substrings

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)

Step by Step Implementation For Palindromic Substrings

public class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (isPalindrome(s, i, j)) {
                    res++;
                }
            }
        }
        return res;
    }
    
    private boolean isPalindrome(String s, int i, int j) {
        while (i < j) {
            if (s.charAt(i++) != s.charAt(j--)) {
                return false;
            }
        }
        return true;
    }
}

class Solution(object):
    def countSubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
        # Solution:
        # We can solve this problem by keeping track of the number of 
        # palindromic substrings as we iterate through the string. 
        # We can do this by maintaining a 2D boolean array, where 
        # dp[i][j] is true if the substring s[i:j+1] is a palindrome. 
        # We can then compute the number of palindromic substrings by 
        # summing up the number of dp[i][j] that are true.
        
        # The base cases are when i == j, which is always a palindrome, 
        # and when i == j - 1. If s[i] == s[j], then it's a palindrome 
        # if dp[i+1][j-1] is a palindrome. Otherwise, it's not a palindrome.
        
        # We can then fill in the rest of the dp array in a bottom-up fashion.
        
        # Time Complexity: O(n^2)
        # Space Complexity: O(n^2)
        
        # Initialize 2D boolean array
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        
        # Base cases
        for i in range(n):
            dp[i][i] = True
        for i in range(n-1):
            dp[i][i+1] = s[i] == s[i+1]
            
        # Fill in rest of array in bottom-up fashion
        for j in range(2, n):
            for i in range(0, j-1):
                dp[i][j] = s[i] == s[j] and dp[i+1][j-1]
                
        # Sum up number of dp[i][j] that are true
        count = 0
        for i in range(n):
            for j in range(n):
                if dp[i][j]:
                    count += 1
                    
        return count

var countSubstrings = function(s) {
    let n = s.length, ans = 0;
    for (let i = 0; i < 2 * n - 1; ++i) {
        let l = i / 2, r = i / 2 + i % 2;
        while (l >= 0 && r < n && s[l] == s[r]) {
            --l;
            ++r;
            ++ans;
        }
    }
    return ans;
};

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.length();
        int ans = 0;
        for(int i = 0; i < n; i++) {
            for(int j = i; j < n; j++) {
                if(isPalindrome(s.substr(i, j-i+1))) {
                    ans++;
                }
            }
        }
        return ans;
    }
    
    bool isPalindrome(string s) {
        int n = s.length();
        for(int i = 0; i < n/2; i++) {
            if(s[i] != s[n-1-i]) {
                return false;
            }
        }
        return true;
    }
};

public class Solution {
    public int CountSubstrings(string s) {
        int count = 0;
        
        for (int i = 0; i < s.Length; i++) {
            //odd length
            count += ExpandFromMiddle(s, i, i);
            //even length
            count += ExpandFromMiddle(s, i, i + 1);
        }
        
        return count;
    }
    
    private int ExpandFromMiddle(string s, int left, int right) {
        int count = 0;
        
        while (left >= 0 && right < s.Length && s[left] == s[right]) {
            count++;
            left--;
            right++;
        }
        
        return count;
    }
}