Special Palindrome Again - Hacker Rank Solution

A string is said to be a special palindromic string if either of two conditions is met:

• All of the characters are the same, e.g. aaa.
• All characters except the middle one are the same, e.g. aadaa.

A special palindromic substring is any substring of a string which meets one of those criteria. Given a string, determine how many special palindromic substrings can be formed from it.

For example, given the string , we have the following special palindromic substrings:.

Function Description

Complete the substrCount function in the editor below. It should return an integer representing the number of special palindromic substrings that can be formed from the given string.

substrCount has the following parameter(s):

• n: an integer, the length of string s
• s: a string

Input Format

The first line contains an integer, , the length of .
The second line contains the string .

Constraints

Each character of the string is a lowercase alphabet, .

Output Format

Print a single line containing the count of total special palindromic substrings.

Sample Input 0

5
asasd

Sample Output 0

7 

Explanation 0

The special palindromic substrings of  are 

Sample Input 1

7
abcbaba

Sample Output 1

10 

Explanation 1

The special palindromic substrings of  are 

Sample Input 2

4
aaaa

Sample Output 2

10

Explanation 2

The special palindromic substrings of  are 

Special Palindrome Again - Hacker Rank Solution

The simplest solution is to check the given condition for every possible substrings and count the valid ones. This approach will take  complexity.

To do this in a little better way we can store the cumulative sum of the occurrences of each character in the string and again count the valid ones by using memoization. This approach will take  complexity.

To solve it efficiently we have to consider  Cases:

Case : All Palindromic substrings have same character:

We can handle this case by simply counting the same continuous character and using formula  (total number of substring possible : Here  is count of Continuous same char).

Case : All Palindromic substrings have same character except one in the middle:

We can handle this case by storing count of same character in another temporary array called same_char_count[] of size and pick each character one-by-one and check its previous and forward character are equal or not, if equal then there are minimum between same_char_count[] and same_char_count[] substring(s) possible.

So, we count total substrings from both cases.

Set by 

rock19

Problem Setter's code:

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n,c,i=0,j,ans=0;
    cin>>n;

    string s;
    cin>>s;

    int same_char_count[n]={0};

    while(i<n) {
        j=i+1,c=1;
        while(j<n && s[i]==s[j]) {
            ++j,++c;
        }

        //total substrings which have all same char(s)
        ans+=(c*(c+1))>>1;
        same_char_count[i]=c;
        i=j;
    }

    for(j=1;j<n-1;++j) {
        if(s[j]==s[j-1]) {
            same_char_count[j] = same_char_count[j-1];
        }

        //odd length substr(s) which has middle element diiferent
        if(s[j-1]==s[j+1] && s[j]!=s[j-1]) {
            ans += min(same_char_count[j-1], same_char_count[j+1]);
        }
    }
    cout<<ans<<endl;

    return 0;
}