Count Special Palindromic Substrings

The basic approach is to create all possible substrings from the given string and then count the number of special palindromic substrings from them.

Algorithm:

• Let N be the length of the given string.
• Initialise a variable “count” with starting value ‘0’ to store the total count of special palindromic substrings.
• Start creating the substrings of the given string using two loops,
• The first loop points towards the starting point of the substring, i = 0 to N-1
  • The second loop points towards the ending point of substring, j = i + 1 to N-1
    • Start another loop that will check for all characters of the substring created
      • If all characters are the same.
      • Or if the length of the substring is odd and only the middle element is different.
      • If such string is found:
        • Increment “count” by 1.
  • Return the variable “count”.

In this approach we will be creating two cases:

1. To get substrings having all characters same
2. To get substrings of odd length with only mid character different

Case1: 

• We will be counting the number of continuous characters that are the same in the given string.  For doing this we simply traverse through the string and keep count of continuous same characters.
• Example: S = aaabcc, now counting the number of continuous characters that are the same in the string. We have 3 a’s and then 2 c’s, so for each character, we will count the number of substrings that can be formed using 3 and 2 characters, using the method explained below.
• Let the above count be “X”, now in order to count the number of substrings having length greater than 1 that can be made using those characters, we will store them in an array too which will be used in the second case.
  • We can count such substrings using the formula:
    • ((X)*(X-1)/2)
    • This formula works as:
      • Count of substrings of length 1 from string of length X = X
      • Count of substrings of length 2 from string of length X = X - 1. (Choosing any of the X - 1 pairs formed by adjacent characters)
      • Similarly we can deduce the total number of substrings: X + (X - 1) + (X - 2).... = X*(X + 1)/2 
      • As we need not to include the substrings having length 1. So we will subtract the count of such substrings. Hence, the overall count turns out to be ((X)*(X - 1)/2)

Case2:

• For this case, we will create an array  that will store the count of the same continuous characters in the string.
  • For example: String: baabaaab,
  • Create an array that will store the count of continuous characters that we calculated in Case 1.
  • The array storing the count will look like: 1 2 2 1 3 3 3 1
• Now, we will pick each character one by one and check whether its previous and next character are equal or not and the current character is different from them.
  • If equal:
    • Add the count of continuous character to the total “count” of special palindromes
  • If not:
    • Add the minimum of the count of continuous same characters on both sides of the middle element to the total “count” of special palindromes.
      • This is because in the above example of string baabaaab, we have 2 a’s before ‘b’ and 3 a’s after ‘b’, now in order to get only the middle element different we would be counting possible substrings from the substring “aabaa”, and the number of substrings formed are 2 i.e equal to the minimum of the two counts.
• Finally return the total “count”.