Krdytkyu

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 <bits/stdc++.h>



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 <= n){

        for(long int i = 0; i <= n - length_sub ; i++){

            string sub = s.substr(i, length_sub);

            //cout << sub << " ";

            string rev_sub(sub);

            reverse(rev_sub.begin(), rev_sub.end());

            //cout << rev_sub;;

            char c = sub[0];

            int flag = 0;

            for(long int j = 0; j < sub.length() / 2; j++){

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

                    flag = 1;

                    break;

                }

            }

            if(flag == 0){

                //cout << " - Specialn";

                count++;

            }

            // else{

            //     cout << "n";

            // }

        }

        length_sub++;

    }

    return count;



}



int main()

{

    ofstream fout(getenv("OUTPUT_PATH"));



    int n;

    cin >> n;

    cin.ignore(numeric_limits<streamsize>::max(), 'n');



    string s;

    getline(cin, s);



    long result = substrCount(n, s);



    fout << result << "n";



    fout.close();



    return 0;

}

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 practice.
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 – 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

First, the things which are bad about the form:

1. #include <bits/stdc++.h> is non-standard and probably far too much.




2. using namespace std; is evil because std is not designed to be imported wholesale, making conflicts and silent changes, now and in future, likely.




3. long substrCount(int n, string s) is also a bad idea. n duplicates s.size() but with the wrong type (it should be string::size_type).




4. The code assumes that input won't fail. That's generally wrong.




5. return 0; is implicit for main().

Now, about your code:

6. All your comments are just a distraction, as they contain cryptic code-fragments. Clean them up.




7. If you want to create a reverse of a range, just initialize the copy with reverse-iterators instead of copying and then reversing. rbegin() and rend() are your friends.



8. 
   

   If you want to know whether a range is all copies of the same element except the middle, take a look at std::count():

   
   
   

   bool my_palindrome = range[range.size() / 2] != range[0]
   
       && std::count(range.begin(), range.end(), range[0]) == range.size() - 1;
   
   

   
   
   

   Making copies, reversing, and then comparing is just superfluous additional work.

   
   


9. 
   

   Fixing all those small things might lead to a significant speed-up, but it doesn't improve the order of your algorithm which is $O(n^2)$.

   
   
   

   For that, move to a different algorithm:

   
   
   
   
   
   1. Start with zero.
   
   
   2. Find runs of identical characters.
   
   
   3. Add the number of substrings for the run, which is $k * (k + 1) / 2$.
   
   
   4. If the run has length one, and the bordering runs consist of identical characters, add the length of the smaller one.
   
   
   
   

   That's $O(n)$, even single-pass.

   
   

Improved version of your function (using C++17 std::string_view as the parameter to avoid any copies, even in the caller, whether he has a std::string or not):

long substrCount(std::string_view s) noexcept {

    char c[3] = {};

    long n[3] = {};

    long r = 0;

    for (auto curr = begin(s), last = end(s), pos = begin(s); curr != last; curr = pos) {

        pos = std::find_if(curr + 1, last, [=](char c){ return c != *curr; });

        std::tie(n[2], n[1], n[0]) = std::make_tuple(n[1], n[0], pos - curr);

        std::tie(c[2], c[1], c[0]) = std::make_tuple(c[1], c[0], *curr);

        r += *n * (*n + 1) / 2;

        if (n[1] == 1 && c[0] == c[2])

            r += std::min(n[0], n[2]);

    }

    return r;

}