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 then comparing 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 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;
}