Write a Java program to count substrings with same first and last characters using recursion
This code recursively counts the number of substrings in a given string that have the same first and last character. Here's how it works:
- The main method initializes a string str and its length n, and then calls the CountSubstring method to count the number of substrings with same first and last characters.
- The CountSubstring method takes in the string str, the starting index i, the ending index j, and the length of the string n.
- If n is 1, then there is only one character in the string, and that character is both the first and last character of the substring, so it returns 1.
- If n is less than or equal to 0, then there are no characters in the string, so it returns 0.
- The method recursively calls itself with the same string str, but with the starting index incremented by 1 and the length of the string decremented by 1, and with the ending index decremented by 1 and the length of the string decremented by 1, and subtracts the result of the recursive call with the starting index incremented and ending index decremented by 1 and the length of the string decremented by 2.
- This effectively counts all substrings that have the same first and last character, including substrings with repeated characters, but also double counts substrings with non-repeating first and last characters. To correct for this, the method checks if the first and last characters of the string are equal, and if they are, it increments the result by 1.
- Finally, the method returns the result.
This algorithm has a time complexity of O(3^n), which is exponential and can be slow for larger strings.
Source Code
class Count_Substring
{
public static void main (String[] args)
{
String str = "XYX";
int n = str.length();
System.out.print("Total substrings with same First and Last Characters : "+ CountSubstring(str, 0, n - 1, n));
}
static int CountSubstring(String str, int i, int j, int n)
{
if (n == 1)
{
return 1;
}
if (n <= 0)
{
return 0;
}
int res = CountSubstring(str, i+1, j, n-1) + CountSubstring(str, i, j-1, n-1) - CountSubstring(str, i+1, j-1, n-2);
if (str.charAt(i) == str.charAt(j))
{
res++;
}
return res;
}
}
Output
Total substrings with same First and Last Characters : 4