Hacker Rank Challenge : Find count of substrings which are special palindrome I am getting timeout for test cases having very large input. 

-= Challenge Link =-

-= Test case example =-

Code is working fine as can be checked on ideone. (Note: Here fout has been replaced with cout.)


  Problem Statement :
  
  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 s = mnonopoo , we have the following special
  palindromic substrings: {m, n, o, n, o, p, o, o, non, ono, opo, oo}.
  
  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, n , the length of s.  The second line
  contains the string .
  
  Constraints
  
  1 ≤ n ≤ 10^6
  
  Each character of the string is a lowercase alphabet, ascii[a-z].
  
  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 s = asasd are {a, s, a, s, d, asa, sas}. 
  
  Sample Input 1

7 
abcbaba

  
  Sample Output 1

10  

  
  Explanation 1
  
  The special palindromic substrings of s = abcbaba are {a, b, c, b, a, b, a, bcb, bab, aba}.
  
  Sample Input 2

4 
aaaa 

  
  Sample Output 2

10

  
  Explanation 2
  
  The special palindromic substrings of s = aaaa are {a, a, a, a, aa, aa, aa, aaa, aaa, aaaa}.


Code:

#include &lt;bits/stdc++.h&gt;

using namespace std;

// Complete the substrCount function below.
long substrCount(int n, string s) {

    long int length_sub = 2;
    long int count = n;
    while(length_sub &lt;= n){
        for(long int i = 0; i &lt;= n - length_sub ; i++){
            string sub = s.substr(i, length_sub);
            //cout &lt;&lt; sub &lt;&lt; " ";
            string rev_sub(sub);
            reverse(rev_sub.begin(), rev_sub.end());
            //cout &lt;&lt; rev_sub;;
            char c = sub[0];
            int flag = 0;
            for(long int j = 0; j &lt; sub.length() / 2; j++){
                if(sub[j] != c || rev_sub[j] != c){
                    flag = 1;
                    break;
                }
            }
            if(flag == 0){
                //cout &lt;&lt; " - Special\n";
                count++;
            }
            // else{
            //     cout &lt;&lt; "\n";
            // }
        }
        length_sub++;
    }
    return count;

}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    int n;
    cin &gt;&gt; n;
    cin.ignore(numeric_limits&lt;streamsize&gt;::max(), '\n');

    string s;
    getline(cin, s);

    long result = substrCount(n, s);

    fout &lt;&lt; result &lt;&lt; "\n";

    fout.close();

    return 0;
}
This

#include &lt;bits/stdc++.h&gt;
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 practice.
See for example


Why should I not #include &lt;bits/stdc++.h&gt;?
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 – why should it
be different from the inner for(long int ...) loop?
The proper data type for string lengths and indices is string::size_type
aka size_t.


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.


Example: The string "mnonopoo" has the following sequences of contiguous 
identical characters

m n o n o p oo


which gives a total

1+1+1+1+1+1+3 = 9


substrings with all identical characters. The number of substrings where
all characters except the middle one are the same around each character are

m n o n o p o o
0+0+1+1+0+1+0+0 = 3