Return to Revisions

This

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

is given by the submission template from HackerRank (so it is not your fault), but note that both lines are generally considered as bad practise. See for example

• Why should I not #include <bits/stdc++.h>?
• Why is "using namespace std" considered bad practice?

on Stack Overflow.

With respect to your

long substrCount(int n, string s)

function:

• The outer while loop could be made a for loop as well.

• The proper data type for string lengths and indices is string::size_type aka size_t. You can also use auto variables to let the compiler infer the type, e.g.

   for(auto j = 0; j < sub.length() / 2; j++)
  

One step to increase the efficiency would be to avoid the creation (and reversal) of the additional strings sub and rev_sub. All tests can be done directly on the original string s. As an example,

if (sub[j] != c || rev_sub[j] != c)

is equivalent to

if (s[i + j] != c || s[i + length_sub - 1 - j] != c) 

Your method checks all \$ n (n-1)/2 \$ substrings of length 2 or more if it is a "special palindromic string.". The following approach seems more efficient to me:

• The number of substrings with all identical characters (e.g. "aaa") can be determined with a single traversal of the string. All sequences of \$ k \$ contiguous identical characters contain \$ k(k+1)/2 \$ substrings with identical characters.

• To determine the number of substrings where characters except the middle one are the same (e.g. "aadaa") traverse the string, and check for each character (e.g. "d") how many identical characters exist to the left and to the right of this character.