🚀Day 19/180 Counting all contiguous substrings starting and ending with the same character.(Using Recursive function)

Counting all contiguous substrings starting and ending with the same character.(Using Recursive function)

#180DaysOfDSA#DailyCodingChallenge #LeetCodeJourney #GeeksforGeeks #CodingNinjas #Codechef #CodeForces #ContinuousLearning #TechCommunity

The provided Java program calculates the number of palindromic substrings in a given string. The main method initializes a string "abcab" and calls the countSubstrs method to compute and print the result.

Here is a detailed explanation of the code:

1. Base Cases:

   • If the length of the substring n is 1, it returns 1 because any single character is a palindrome.

   • If n is less than or equal to 0, it returns 0 because there are no valid substrings to check.

2. Recursive Calculation:

   • The function recursively calculates the number of palindromic substrings by:

     • Excluding the current character at index i and considering the substring from i+1 to j.

     • Excluding the current character at index j and considering the substring from i to j-1.

     • Excluding both characters at index i and j and considering the substring from i+1 to j-1.

   • It subtracts the count of substrings excluding both i and j to avoid double-counting.

3. Checking for Palindromes:

   • If the characters at indices i and j are equal, it increments the result by 1 since this pair forms a palindromic substring.

4. Main Method:

   • The main method initializes the string "abcab" and its length n.

   • It then calls the countSubstrs method with initial values 0 (start index), n-1 (end index), and n (length of the substring).

   • The result is printed to the console.

Here is the provided code with comments for better understanding:

public class Main {
    // Method to count palindromic substrings
    public static int countSubstrs(String str, int i, int j, int n) {
        // Base case: single character substring
        if (n == 1) {
            return 1;
        }
        // Base case: invalid substring
        if (n <= 0) {
            return 0;
        }

        // Recursive case
        int res = countSubstrs(str, i + 1, j, n - 1) +
                  countSubstrs(str, i, j - 1, n - 1) -
                  countSubstrs(str, i + 1, j - 1, n - 2);

        // Check if the current substring is a palindrome
        if (str.charAt(i) == str.charAt(j)) {
            res++;
        }

        return res;
    }

    // Main method
    public static void main(String[] args) {
        String str = "abcab";
        int n = str.length();
        System.out.print(countSubstrs(str, 0, n - 1, n));
    }
}

When executed, the program prints 7, which is the number of palindromic substrings in the string "abcab".