Special Palindrome Again Solution

This is one of the medium difficulty problems in the string manipulation section of hackerrank’s interview preparation kit problem set. Link here.

The problem states that given a string s you need to find all special palindromic substrings. Any string is special palindromic if and only if

1- All the characters are the same.

2- The middle character is different but the rest are the same.

“aaa” is special palindromic, “aaaabb” is not.

Solution

The approach you need to use is to make multiple passes of the string. There is no need to get all substrings. In fact that would make our submission timeout. First we count all substrings that fit the first case. To do this we can keep two arrays. One group all contiguous characters of same value and one to count occurrences .

For instance “aaa” would become [‘a’: 3], “aaaabb" becomes [‘a’: 4, ‘b’:2]. Now each of these represent a character occurring n times. If we add n*n+1/2 to our result for each of these we will count all substrings that match case 1.

For case 2 we find all chars that occur once, have neighbouring characters and these neighbouring characters are the same character. For each of these cases we add to our result the min of both neighbours. Those match case 2 and that’s it.

To illustrate this “aba” results in [‘a’:1, ‘b’:1, ‘a’:1]. Here ‘b’ has neighbouring characters, and both are the same. In this case we would add the min of both which is 1 “aba”. This represents the number of palindromes that can be formed for case 2.

Code

FULL SOLUTION ON GITHUB

long substrCount(int n, string s) {

string cs;
long ep_count;
char curr_char;
const char* s_chars;
vector<int> ocurr(n);
    curr_char= '\0';
s_chars = s.c_str();
int str_index = -1;
for(int i = 0; i < n ; i++){
if(i == 0 || s_chars[i] != curr_char){
str_index++;
curr_char = s_chars[i];
cs.append(1, curr_char);
}
ocurr[ str_index ]++;
}

for(int i = 0; i < cs.size(); i++){
ep_count+=(ocurr[i]*(ocurr[i]+1))/2;
}

for(int i = 1; i < cs.size()-1 ; i++){
if( ocurr[i] == 1 && cs[i-1] == cs[i+1] ){
ep_count+= min(ocurr[i-1], ocurr[i+1]);
}
}
return ep_count;
}