Count all palindromic Substrings for each character in a given String

Given a string S of length n, for each character S[i], the task is to find the number of palindromic substrings of length K such that no substring should contain S[i], the task is to return an array A of length n, where A[i] is the count of palindromic substrings of length K which does not include the character S[i].

Examples:

Input: S = “aababba”, K = 2
Output : A[] = [1 1 2 2 1 1 2]
Explanation: A[0] = 1 => removing char s[0] = ‘a’ only one palindromic substring of length 2 is possible i.e. “bb”
A[1] = 1 => removing char s[1] = ‘a’ only one palindromic substring of length 2 is possible i.e. “bb” 
A[2] = 2 => removing char s[2] = ‘b’ two palindromic substring of length 2 are possible i.e. “aa” and “bb”
A[3] = 2 => removing char s[3] = ‘a’ two palindromic substring of length 2 are possible i.e. “aa” and “bb” 
A[4] = 1 => removing char s[4] = ‘b’ only one palindromic substring of length 2 is possible i.e. “aa” 
A[5] = 1 => removing char s[5] = ‘b’ only one palindromic substring of length 2 is possible i.e. “aa” 
A[6] = 2 => removing char s[6] = ‘a’ two palindromic substring of length 2 are possible i.e. “aa” and “bb” 

Input: S = “abbab”, K = 2
Output: A[] = [1 0 0 1 1]
Explanation: A[0] = 1 => removing char s[0] = ‘a’ only one palindromic substring of length 2 is possible i.e. “bb”
A[1] = 1 => removing char s[1] = ‘b’ no palindromic substring of length 2 is possible
A[2] = 2 => removing char s[2] = ‘b’ no palindromic substring of length 2 is possible
A[3] = 2 => removing char s[3] = ‘a’ only one palindromic substring of length 2 is possible i.e. “bb”
A[4] = 1 => removing char s[4] = ‘b’ only one palindromic substring of length 2 is possible i.e. “bb”

Approach: To solve the problem follow the below steps:

• For character S[i] of the string, we need to find palindromic substrings of length K such that the substrings don’t include S[i]. This approach requires one loop to iterate the string and two separate inner for loops because we don’t have to include the character S[i] so we need to skip the entire range for which S[i] is included in any substring.
• Run a loop to iterate the string from i = 0 to i < length of string. 
• The first inner loop will run from j = 0 to j ≤ i – K, then the last substring before S[i] will start from i – K and end at i – 1 which won’t include S[i].
• The second inner loop starts from j = i + 1 to n – 1.
• For each substring, check if it is a palindrome, then increment the counter for that character S[i].

Below are the steps for the above approach:

• Create an array A[] to store the count of the number of palindromic substrings for S[i].
• Run a loop to iterate the string from i = 0 to i < S.length.
• Initialize a counter-variable count = 0.
• The first inner loop runs from j = 0 to j = i – K and generates a substring from j of length K to check if it is a palindrome, incrementing the counter.
• The second inner loop runs from j = i+1 to j = l – 1 and generates a substring from j of length k to check if it is a palindrome, and increment the counter.
• When both inner loop ends, update A[i] = count
• Return the array A[].

Below is the implementation for the above approach:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;

// function to check if a string is palindrome
bool isPalin(string s, int l)
{
    for (int i = 0; i < l; i++) {
        if (s[i] != s[l - i - 1])
            return false;
    }
    return true;
}

// function to count the number of paldinromic
// substrings for each character of a string
void findCount(string s, int l, int k, int A[])
{
    for (int i = 0; i < s.length(); i++) {
        int count = 0;

        // loop 1
        for (int j = 0; j <= i - k; j++) {
            string sub = s.substr(j, k);
            if (isPalin(sub, k))
                count++;
        }

        // loop 2
        for (int j = i + 1; j < l; j++) {
            string sub = s.substr(j, k);
            if (isPalin(sub, k))
                count++;
        }

        A[i] = count;
    }
}

// Driver fucntion
int main()
{
    string s = "aababba"; // given string
    int l = 7; // length of string
    int k = 2; // length of substring

    // array to store the count
    int A[s.length()];

    // function call
    findCount(s, l, k, A);

    cout << "Count of palindromic substrings for "
         << "each character of string s is: [ ";
    for (int i = 0; i < s.length(); i++)
        cout << A[i] << " ";
    cout << "]" << '\n';
}

Count of palindromic substrings for each character of string s is: [ 1 1 2 2 1 1 2 ]

Time Complexity: O(l²) where l is the length of the string
Auxiliary Space: O(l) where l is the length of the Resultant Array

Given a string S of length n, for each character S[i], the task is to find the number of palindromic substrings of length K such that no substring should contain S[i], the task is to return an array A of length n, where A[i] is the count of palindromic substrings of length K which does not include the character S[i].

Examples:

Input: S = “aababba”, K = 2
Output : A[] = [1 1 2 2 1 1 2]
Explanation: A[0] = 1 => removing char s[0] = ‘a’ only one palindromic substring of length 2 is possible i.e. “bb”
A[1] = 1 => removing char s[1] = ‘a’ only one palindromic substring of length 2 is possible i.e. “bb” 
A[2] = 2 => removing char s[2] = ‘b’ two palindromic substring of length 2 are possible i.e. “aa” and “bb”
A[3] = 2 => removing char s[3] = ‘a’ two palindromic substring of length 2 are possible i.e. “aa” and “bb” 
A[4] = 1 => removing char s[4] = ‘b’ only one palindromic substring of length 2 is possible i.e. “aa” 
A[5] = 1 => removing char s[5] = ‘b’ only one palindromic substring of length 2 is possible i.e. “aa” 
A[6] = 2 => removing char s[6] = ‘a’ two palindromic substring of length 2 are possible i.e. “aa” and “bb” 

Input: S = “abbab”, K = 2
Output: A[] = [1 0 0 1 1]
Explanation: A[0] = 1 => removing char s[0] = ‘a’ only one palindromic substring of length 2 is possible i.e. “bb”
A[1] = 1 => removing char s[1] = ‘b’ no palindromic substring of length 2 is possible
A[2] = 2 => removing char s[2] = ‘b’ no palindromic substring of length 2 is possible
A[3] = 2 => removing char s[3] = ‘a’ only one palindromic substring of length 2 is possible i.e. “bb”
A[4] = 1 => removing char s[4] = ‘b’ only one palindromic substring of length 2 is possible i.e. “bb”

Approach: To solve the problem follow the below steps:

• For character S[i] of the string, we need to find palindromic substrings of length K such that the substrings don’t include S[i]. This approach requires one loop to iterate the string and two separate inner for loops because we don’t have to include the character S[i] so we need to skip the entire range for which S[i] is included in any substring.
• Run a loop to iterate the string from i = 0 to i < length of string. 
• The first inner loop will run from j = 0 to j ≤ i – K, then the last substring before S[i] will start from i – K and end at i – 1 which won’t include S[i].
• The second inner loop starts from j = i + 1 to n – 1.
• For each substring, check if it is a palindrome, then increment the counter for that character S[i].

Below are the steps for the above approach:

• Create an array A[] to store the count of the number of palindromic substrings for S[i].
• Run a loop to iterate the string from i = 0 to i < S.length.
• Initialize a counter-variable count = 0.
• The first inner loop runs from j = 0 to j = i – K and generates a substring from j of length K to check if it is a palindrome, incrementing the counter.
• The second inner loop runs from j = i+1 to j = l – 1 and generates a substring from j of length k to check if it is a palindrome, and increment the counter.
• When both inner loop ends, update A[i] = count
• Return the array A[].

Below is the implementation for the above approach:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;

// function to check if a string is palindrome
bool isPalin(string s, int l)
{
    for (int i = 0; i < l; i++) {
        if (s[i] != s[l - i - 1])
            return false;
    }
    return true;
}

// function to count the number of paldinromic
// substrings for each character of a string
void findCount(string s, int l, int k, int A[])
{
    for (int i = 0; i < s.length(); i++) {
        int count = 0;

        // loop 1
        for (int j = 0; j <= i - k; j++) {
            string sub = s.substr(j, k);
            if (isPalin(sub, k))
                count++;
        }

        // loop 2
        for (int j = i + 1; j < l; j++) {
            string sub = s.substr(j, k);
            if (isPalin(sub, k))
                count++;
        }

        A[i] = count;
    }
}

// Driver fucntion
int main()
{
    string s = "aababba"; // given string
    int l = 7; // length of string
    int k = 2; // length of substring

    // array to store the count
    int A[s.length()];

    // function call
    findCount(s, l, k, A);

    cout << "Count of palindromic substrings for "
         << "each character of string s is: [ ";
    for (int i = 0; i < s.length(); i++)
        cout << A[i] << " ";
    cout << "]" << '\n';
}

Count of palindromic substrings for each character of string s is: [ 1 1 2 2 1 1 2 ]

Time Complexity: O(l²) where l is the length of the string
Auxiliary Space: O(l) where l is the length of the Resultant Array