Count palindromic characteristics of a String in Java
Palindromes, symmetrical sequences of characters, are a fascinating subject in linguistics, mathematics, and computer science. Researchers use methodologies like combinatorics, algorithm design, and string manipulation to count palindromic characteristics within a string. Efficient computation of these counts is challenging, especially for large or complex strings. Understanding these dynamics is crucial for text processing, pattern recognition, bioinformatics, and data compression.
Example:
Input: str = “racecar”
Output: 10 1 0 0 0 0 0
Explanation: The string "racecar" has 10 1-palindromic substrings and 1 2-palindromic substring, meeting 2-palindrome conditions. No substrings meet k-palindrome conditions, resulting in 0 counts.
Using Dynamic Programming
Algorithm
Step1:Initialize 2D boolean array `P` and integer array `Kpal` with MAX_STR_LEN` size.
Step2:Define the `checkSubStrPal` method to mark single and adjacent characters as palindromes.
Step 3: Use dynamic programming to mark palindromes of length greater than 2.
Step4:Define `countKPalindromes` method to recursively count k-palindromes.
Step 5: Calculate the middle index `mid` based on substring length.
Step 6: Call `countKPalindromes` with updated parameters.
Step 7: Define the `printKPalindromes` method to print the number of k-palindromic substrings.
Step 8: Initialize a string `s` in the `main` method.
Here is an implementation of counting palindromic characteristics of a string using dynamic programming :
FileName:PalindromeCounter.java
public class PalindromeCounter { static int MAX_STR_LEN = 1000; static boolean[][] P = new boolean[MAX_STR_LEN][MAX_STR_LEN]; static int[] Kpal = new int[MAX_STR_LEN]; // Function to check whether a substring is palindrome or not static void checkSubStrPal(String str, int n) { // Initialize the P table for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { P[i][j] = false; } Kpal[i] = 0; } // Palindrome of single length for (int i = 0; i < n; i++) { P[i][i] = true; } // Palindrome of length 2 for (int i = 0; i < n - 1; i++) { if (str.charAt(i) == str.charAt(i + 1)) { P[i][i + 1] = true; } } // Palindromes of length more than 2 for (int gap = 2; gap < n; gap++) { for (int i = 0; i < n - gap; i++) { int j = gap + i; if (str.charAt(i) == str.charAt(j) && P[i + 1][j - 1]) { P[i][j] = true; } } } } // Function to recursively count k-palindromes static void countKPalindromes(int i, int j, int k) { // Terminating condition for a k-palindrome if (i == j) { Kpal[k]++; return; } // Terminating condition for a non-k-palindrome if (!P[i][j]) { return; } // Increase the counter for the string if it is a k-palindrome Kpal[k]++; // Mid is the middle pointer of the string int mid = (i + j) / 2; // Adjust mid based on the length of the string if ((j - i + 1) % 2 == 1) { mid--; } // Check if it is a (k+1)-palindrome or not countKPalindromes(i, mid, k + 1); } // Function to print the number of k-palindromic substrings static void printKPalindromes(String s) { // Finding all palindromic substrings of the given string int n = s.length(); checkSubStrPal(s, n); // Counting k-palindromes for every substring of the given string for (int i = 0; i < n; i++) { for (int j = 0; j < n - i; j++) { countKPalindromes(j, j + i, 1); } } for (int i = 1; i <= n; i++) { System.out.print(Kpal[i] + " "); } System.out.println(); } public static void main(String args[]) { String s = "racecar"; printKPalindromes(s); } }
Output:
10 1 0 0 0 0 0
Complexity analysis: The above approach has a time complexity of O(n^2 log n) due to its outer, middle, and palindrome checks, and the space complexity is O(n^2) due to the 2D boolean array `P`, which has dimensions of n x n.