Count palindromic characteristics of a String

Improve

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 : abbaOutput : 6 1 0 0Explanation : "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 : abacabaOutput : 12 4 1 0 0 0 0Explanation : "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

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

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()

Last Updated : 02 Mar, 2023

Like Article

Save Article

Palindrome by swapping only one character

Number of positions where a letter can be inserted such that a string becomes palindrome

Share your thoughts in the comments

Count palindromic characteristics of a String - GeeksforGeeks (2024)

C++

Java

Python3

C#

PHP

Javascript

Please Login to comment...