Return to Revisions

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 is just superfluous additional work.

1. 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 to avoid any copies):

long substrCount(std::string_view s) noexcept {
    char c[3] = {};
    long n[3] = {};
    long r = 0;
    auto count = [&]{
        r += *n * (*n + 1) / 2;
        if (n[1] == 1 && c[0] == c[2])
            r += std::min(n[0], n[2]);
    };
    for (auto x : s) {
        if (x == *c) {
            ++*n;
        } else {
            count();
            c[2] = c[1];
            c[1] = c[0];
            c[0] = x;
            n[2] = n[1];
            n[1] = n[0];
            n[0] = 1;
        }
    }
    count();
    return r;
}