Count palindromic characteristics of a String
Given a string s of length n, count the number of substrings having different types of palindromic characteristics.
Palindromic Characteristic is the number of k-palindromes in a string where k lies in range [0, n).
A string is 1-palindrome(or simply palindrome) if and only if it reads the same backward as it reads forward.
A string is k-palindrome (k > 1) if and only if :
- Its left half is equal to its right half.
- Its left half and right half should be non-empty (k – 1)-palindrome. The left half of a string of length ‘t’ is its prefix of length ?t/2?, and the right half is the suffix of the same length.
Note: Each substring is counted as many times as it appears in the string. For example, in the string “aaa” the substring “a” appears 3 times.
Examples :
Input : abba Output : 6 1 0 0 Explanation : "6" 1-palindromes = "a", "b", "b", "a", "bb", "abba". "1" 2-palindrome = "bb". Because "b" is 1-palindrome and "bb" has both left and right parts equal. "0" 3-palindrome and 4-palindrome. Input : abacaba Output : 12 4 1 0 0 0 0 Explanation : "12" 1-palindromes = "a", "b", "a", "c", "a", "b", "a", "aba", "aca", "aba", "bacab", "abacaba". "4" 2-palindromes = "aba", "aca", "aba", "abacaba". Because "a" and "aba" are 1-palindromes. NOTE : "bacab" is not 2-palindrome as "ba" is not 1-palindrome. "1" 3-palindrome = "abacaba". Because is "aba" is 2-palindrome. "0" other k-palindromes where 4 < = k < = 7.
Approach:
Take a string s and say it is a 1-palindrome and checking its left half also turns out to be a 1-palindrome then, obviously its right part will always be equal to the left part (as the string is also a 1-palindrome) making the original string to be 2-palindrome.
Now, similarly, checking the left half of the string, it also turns out to be a 1-palindrome then it will make the left half to be 2-palindrome and hence, making the original string to be 3-palindrome and so on checking it till only 1 alphabet is left or the part is not a 1-palindrome.
Let’s take string = “abacaba”. As known “abacaba” is 1-palindrome. So, when checking for its left half “aba”, which is also a 1-palindrome, it makes “abacaba” a 2-palindrome. Then, check for “aba”‘s left half “a” which is also a 1-palindrome. So it makes “aba” a 2-palindrome and “aba” makes “abacaba” a 3-palindrome. So in other words, if a string is a k-palindrome then it is also a (k-1)-palindrome, (k-2)-palindrome, and so on till 1-palindrome. Code for the same is given below which firsts check each and every substring if it is a palindrome or not and then counts the number of k-palindromic substrings recursively in logarithmic time.
Below is the implementation of above approach :
C++
// A C++ program which counts different // palindromic characteristics of a string. #include <bits/stdc++.h> using namespace std; const int MAX_STR_LEN = 1000; bool P[MAX_STR_LEN][MAX_STR_LEN]; int Kpal[MAX_STR_LEN]; // A C++ function which checks whether a // substring str[i..j] of a given string // is a palindrome or not. void checkSubStrPal(string str, int n) { // P[i][j] = true if substring str // [i..j] is palindrome, else false memset (P, false , sizeof (P)); // 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[i] == str[i + 1]) P[i][i + 1] = true ; // Palindromes of length more than 2. // This loop is similar to Matrix Chain // Multiplication. We start with a gap of // length 2 and fill P table in a way that // gap between starting and ending indexes // increases one by one by outer loop. for ( int gap = 2; gap < n; gap++) { // Pick starting point for current gap for ( int i = 0; i < n - gap; i++) { // Set ending point int j = gap + i; // If current string is palindrome if (str[i] == str[j] && P[i + 1][j - 1]) P[i][j] = true ; } } } // A C++ function which recursively // counts if a string str [i..j] is // a k-palindromic string or not. void countKPalindromes( int i, int j, int k) { // terminating condition for a // string which is a k-palindrome. if (i == j) { Kpal[k]++; return ; } // terminating condition for a // string which is not a k-palindrome. if (P[i][j] == false ) return ; // increases the counter for the // string if it is a k-palindrome. Kpal[k]++; // mid is middle pointer of // the string str [i...j]. int mid = (i + j) / 2; // if length of string which is // (j - i + 1) is odd than we have // to subtract one from mid. // else if even then no change. if ((j - i + 1) % 2 == 1) mid--; // if the string is k-palindrome // then we check if it is a // (k+1) - palindrome or not by // just sending any of one half of // the string to the Count_k_Palindrome // function. countKPalindromes(i, mid, k + 1); } void printKPalindromes(string s) { // Count of k-palindromes is equal // to zero initially. memset (Kpal, 0, sizeof (Kpal)); // Finding all palindromic // substrings of given string int n = s.length(); checkSubStrPal(s, n); // counting k-palindromes for each and // every substring of given string. . for ( int i = 0; i < n; i++) for ( int j = 0; j < n - i; j++) countKPalindromes(j, j + i, 1); // Output the number of K-palindromic // substrings of a given string. for ( int i = 1; i <= n; i++) cout << Kpal[i] << " " ; cout << "\n" ; } // Driver code int main() { string s = "abacaba" ; printKPalindromes(s); return 0; } |
Java
// Java program which counts // different palindromic // characteristics of a string. import java.io.*; class GFG { 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 which checks // whether a substring // str[i..j] of a given // string is a palindrome or not. static void checkSubStrPal(String str, int n) { // P[i,j] = true if substring // str [i..j] is palindrome, // else false for ( int i = 0 ; i < MAX_STR_LEN; i++) { for ( int j = 0 ; j < MAX_STR_LEN; 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. This loop // is similar to Matrix // Chain Multiplication. // We start with a gap of // length 2 and fill P table // in a way that gap between // starting and ending indexes // increases one by one by // outer loop. for ( int gap = 2 ; gap < n; gap++) { // Pick starting point // for current gap for ( int i = 0 ; i < n - gap; i++) { // Set ending point int j = gap + i; // If current string // is palindrome if (str.charAt(i) == str.charAt(j) && P[i + 1 ][j - 1 ]) P[i][j] = true ; } } } // A function which recursively // counts if a string str [i..j] is // a k-palindromic string or not. static void countKPalindromes( int i, int j, int k) { // terminating condition // for a string which is // a k-palindrome. if (i == j) { Kpal[k]++; return ; } // terminating condition for // a string which is not a // k-palindrome. if (P[i][j] == false ) return ; // increases the counter // for the string if it // is a k-palindrome. Kpal[k]++; // mid is middle pointer of // the string str [i...j]. int mid = (i + j) / 2 ; // if length of string which // is (j - i + 1) is odd than // we have to subtract one // from mid else if even then // no change. if ((j - i + 1 ) % 2 == 1 ) mid--; // if the string is k-palindrome // then we check if it is a // (k+1) - palindrome or not // by just sending any of one // half of the string to the // Count_k_Palindrome function. countKPalindromes(i, mid, k + 1 ); } static void printKPalindromes(String s) { // Finding all palindromic // substrings of given string int n = s.length(); checkSubStrPal(s, n); // counting k-palindromes for // each and every substring // of given string. . for ( int i = 0 ; i < n; i++) for ( int j = 0 ; j < n - i; j++) countKPalindromes(j, j + i, 1 ); // Output the number of // K-palindromic substrings // of a given string. for ( int i = 1 ; i <= n; i++) System.out.print(Kpal[i] + " " ); System.out.println(); } // Driver code public static void main(String args[]) { String s = "abacaba" ; printKPalindromes(s); } } // This code is contributed by // Manish Shaw(manishshaw1) |
Python3
# Python program which counts # different palindromic # characteristics of a string. MAX_STR_LEN = 1000 ; P = [[ 0 for x in range (MAX_STR_LEN)] for y in range (MAX_STR_LEN)] ; for i in range ( 0 , MAX_STR_LEN) : for j in range ( 0 , MAX_STR_LEN) : P[i][j] = False ; Kpal = [ 0 ] * MAX_STR_LEN; # def which checks # whether a substr[i..j] # of a given is a # palindrome or not. def checkSubStrPal( str , n) : global P, Kpal, MAX_STR_LEN; # P[i,j] = True if substr # [i..j] is palindrome, # else False for i in range ( 0 , MAX_STR_LEN) : for j in range ( 0 , MAX_STR_LEN) : P[i][j] = False ; Kpal[i] = 0 ; # palindrome of # single length for i in range ( 0 , n) : P[i][i] = True ; # palindrome of # length 2 for i in range ( 0 , n - 1 ) : if ( str [i] = = str [i + 1 ]) : P[i][i + 1 ] = True ; # Palindromes of length more # than 2. This loop is similar # to Matrix Chain Multiplication. # We start with a gap of length # 2 and fill P table in a way # that gap between starting and # ending indexes increases one # by one by outer loop. for gap in range ( 2 , n) : # Pick starting point # for current gap for i in range ( 0 , n - gap) : # Set ending point j = gap + i; # If current string # is palindrome if ( str [i] = = str [j] and P[i + 1 ][j - 1 ]) : P[i][j] = True ; # A Python def which # recursively counts if # a str [i..j] is a # k-palindromic or not. def countKPalindromes(i, j, k) : global Kpal, P; # terminating condition # for a which is a # k-palindrome. if (i = = j) : Kpal[k] = Kpal[k] + 1 ; return ; # terminating condition # for a which is not a # k-palindrome. if (P[i][j] = = False ) : return ; # increases the counter # for the if it is a # k-palindrome. Kpal[k] = Kpal[k] + 1 ; # mid is middle pointer # of the str [i...j]. mid = int ((i + j) / 2 ); # if length of which is # (j - i + 1) is odd than # we have to subtract one # from mid else if even # then no change. if ((j - i + 1 ) % 2 = = 1 ) : mid = mid - 1 ; # if the is k-palindrome # then we check if it is a # (k+1) - palindrome or not # by just sending any of # one half of the to the # Count_k_Palindrome def. countKPalindromes(i, mid, k + 1 ); def printKPalindromes(s) : global P, Kpal, MAX_STR_LEN; # Finding all palindromic # substrings of given string n = len (s); checkSubStrPal(s, n); # counting k-palindromes # for each and every sub # of given string. . for i in range ( 0 , n) : for j in range ( 0 , n - i) : countKPalindromes(j, j + i, 1 ); # Output the number of # K-palindromic substrings # of a given string. for i in range ( 1 , n + 1 ) : print (Kpal[i], end = " " ); print (); # Driver code s = "abacaba" ; printKPalindromes(s); # This code is contributed by # Manish Shaw(manishshaw1) |
C#
// C# program which counts // different palindromic // characteristics of a string. using System; class GFG { static int MAX_STR_LEN = 1000; static bool [,]P = new bool [MAX_STR_LEN, MAX_STR_LEN]; static int []Kpal = new int [MAX_STR_LEN]; // function which checks whether // a substring str[i..j] of a // given string is a palindrome or not. static void checkSubStrPal( string str, int n) { // P[i,j] = true if substring str // [i..j] is palindrome, else false for ( int i = 0; i < MAX_STR_LEN; i++) { for ( int j = 0; j < MAX_STR_LEN; 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[i] == str[i + 1]) P[i, i + 1] = true ; // Palindromes of length more // than 2. This loop is similar // to Matrix Chain Multiplication. // We start with a gap of length 2 // and fill P table in a way that // gap between starting and ending // indexes increases one by one by // outer loop. for ( int gap = 2; gap < n; gap++) { // Pick starting point // for current gap for ( int i = 0; i < n - gap; i++) { // Set ending point int j = gap + i; // If current string // is palindrome if (str[i] == str[j] && P[i + 1, j - 1]) P[i, j] = true ; } } } // A C++ function which recursively // counts if a string str [i..j] is // a k-palindromic string or not. static void countKPalindromes( int i, int j, int k) { // terminating condition for a // string which is a k-palindrome. if (i == j) { Kpal[k]++; return ; } // terminating condition for // a string which is not a // k-palindrome. if (P[i, j] == false ) return ; // increases the counter for the // string if it is a k-palindrome. Kpal[k]++; // mid is middle pointer of // the string str [i...j]. int mid = (i + j) / 2; // if length of string which is // (j - i + 1) is odd than we have // to subtract one from mid. // else if even then no change. if ((j - i + 1) % 2 == 1) mid--; // if the string is k-palindrome // then we check if it is a // (k+1) - palindrome or not // by just sending any of one // half of the string to the // Count_k_Palindrome function. countKPalindromes(i, mid, k + 1); } static void printKPalindromes( string s) { // Finding all palindromic // substrings of given string int n = s.Length; checkSubStrPal(s, n); // counting k-palindromes for each and // every substring of given string. . for ( int i = 0; i < n; i++) for ( int j = 0; j < n - i; j++) countKPalindromes(j, j + i, 1); // Output the number of K-palindromic // substrings of a given string. for ( int i = 1; i <= n; i++) Console.Write(Kpal[i] + " " ); Console.WriteLine(); } // Driver code static void Main() { string s = "abacaba" ; printKPalindromes(s); } } // This code is contributed by // Manish Shaw(manishshaw1) |
PHP
<?php // PHP program which counts // different palindromic // characteristics of a string. $MAX_STR_LEN = 1000; $P = array ( array ()); $Kpal = array_fill (0, $MAX_STR_LEN , 0); for ( $i = 0; $i < $MAX_STR_LEN ; $i ++) { for ( $j = 0; $j < $MAX_STR_LEN ; $j ++) $P [ $i ][ $j ] = false; } // function which checks // whether a substr[i..j] // of a given is a // palindrome or not. function checkSubStrPal( $str , $n ) { global $P , $Kpal , $MAX_STR_LEN ; // P[i,j] = true if substr // [i..j] is palindrome, else false for ( $i = 0; $i < $MAX_STR_LEN ; $i ++) { for ( $j = 0; $j < $MAX_STR_LEN ; $j ++) $P [ $i ][ $j ] = false; $Kpal [ $i ] = 0; } // palindrome of // single length for ( $i = 0; $i < $n ; $i ++) $P [ $i ][ $i ] = true; // palindrome of // length 2 for ( $i = 0; $i < $n - 1; $i ++) if ( $str [ $i ] == $str [ $i + 1]) $P [ $i ][ $i + 1] = true; // Palindromes of length more // than 2. This loop is similar // to Matrix Chain Multiplication. // We start with a gap of length // 2 and fill P table in a way // that gap between starting and // ending indexes increases one // by one by outer loop. for ( $gap = 2; $gap < $n ; $gap ++) { // Pick starting point // for current gap for ( $i = 0; $i < $n - $gap ; $i ++) { // Set ending point $j = $gap + $i ; // If current string // is palindrome if ( $str [ $i ] == $str [ $j ] && $P [ $i + 1][ $j - 1]) $P [ $i ][ $j ] = true; } } } // A PHP function which // recursively counts if // a str [i..j] is a // k-palindromic or not. function countKPalindromes( $i , $j , $k ) { global $Kpal , $P ; // terminating condition for a // which is a k-palindrome. if ( $i == $j ) { $Kpal [ $k ]++; return ; } // terminating condition // for a which is not a // k-palindrome. if ( $P [ $i ][ $j ] == false) return ; // increases the counter // for the if it is a // k-palindrome. $Kpal [ $k ]++; // mid is middle pointer // of the str [i...j]. $mid = ( $i + $j ) / 2; // if length of which is // (j - i + 1) is odd than // we have to subtract one // from mid else if even // then no change. if (( $j - $i + 1) % 2 == 1) $mid --; // if the is k-palindrome // then we check if it is a // (k+1) - palindrome or not // by just sending any of // one half of the to the // Count_k_Palindrome function. countKPalindromes( $i , $mid , $k + 1); } function printKPalindromes( $s ) { global $P , $Kpal , $MAX_STR_LEN ; // Finding all palindromic // substrings of given string $n = strlen ( $s ); checkSubStrPal( $s , $n ); // counting k-palindromes // for each and every sub // of given string. . for ( $i = 0; $i < $n ; $i ++) for ( $j = 0; $j < $n - $i ; $j ++) countKPalindromes( $j , $j + $i , 1); // Output the number of // K-palindromic substrings // of a given string. for ( $i = 1; $i <= $n ; $i ++) echo ( $Kpal [ $i ] . " " ); echo ( "\n" ); } // Driver code $s = "abacaba" ; printKPalindromes( $s ); // This code is contributed by // Manish Shaw(manishshaw1) ?> |
Javascript
// A javascript program which counts different // palindromic characteristics of a string. let MAX_STR_LEN = 1000; let P = new Array(MAX_STR_LEN); for (let i = 0; i < MAX_STR_LEN; i++){ P[i] = new Array(MAX_STR_LEN); } let Kpal = new Array(MAX_STR_LEN); // A JavaScript function which checks whether a // substring str[i..j] of a given string // is a palindrome or not. function checkSubStrPal(str, n) { // P[i][j] = true if substring str // [i..j] is palindrome, else false for (let i = 0; i < P.length; i++){ for (let j = 0; j < P[0].length; j++){ P[i][j] = false ; } } // palindrome of single length for (let i = 0; i < n; i++) P[i][i] = true ; // palindrome of length 2 for (let i = 0; i < n - 1; i++) if (str[i] == str[i + 1]) P[i][i + 1] = true ; // Palindromes of length more than 2. // This loop is similar to Matrix Chain // Multiplication. We start with a gap of // length 2 and fill P table in a way that // gap between starting and ending indexes // increases one by one by outer loop. for (let gap = 2; gap < n; gap++) { // Pick starting point for current gap for (let i = 0; i < n - gap; i++) { // Set ending point let j = gap + i; // If current string is palindrome if (str[i] == str[j] && P[i + 1][j - 1]) P[i][j] = true ; } } } // A C++ function which recursively // counts if a string str [i..j] is // a k-palindromic string or not. function countKPalindromes(i, j, k) { // terminating condition for a // string which is a k-palindrome. if (i == j) { Kpal[k] = Kpal[k] + 1; return ; } // terminating condition for a // string which is not a k-palindrome. if (P[i][j] == false ) return ; // increases the counter for the // string if it is a k-palindrome. Kpal[k] = Kpal[k] + 1; // mid is middle pointer of // the string str [i...j]. let mid = Math.floor((i + j) / 2); // if length of string which is // (j - i + 1) is odd than we have // to subtract one from mid. // else if even then no change. if ((j - i + 1) % 2 == 1) mid = mid - 1; // if the string is k-palindrome // then we check if it is a // (k+1) - palindrome or not by // just sending any of one half of // the string to the Count_k_Palindrome // function. countKPalindromes(i, mid, k + 1); } function printKPalindromes(s) { // Count of k-palindromes is equal // to zero initially. for (let i = 0; i < Kpal.length; i++){ Kpal[i] = 0; } // Finding all palindromic // substrings of given string let n = s.length; checkSubStrPal(s, n); // counting k-palindromes for each and // every substring of given string. . for (let i = 0; i < n; i++) for (let j = 0; j < n - i; j++) countKPalindromes(j, j + i, 1); // Output the number of K-palindromic // substrings of a given string. for (let i = 1; i <= n; i++) console.log(Kpal[i] + " " ); } // Driver code let s = "abacaba" ; printKPalindromes(s); |
Output
12 4 1 0 0 0 0
Complexity Analysis:
- Time Complexity : O()
- Auxiliary Space : O()