6
\$\begingroup\$

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 << " - Special\n";
                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;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Not sure it belongs here... codereview isn't about improving algorithms as far as I know. That said, a hint: don't create an endless stream of substrings when you can use iterators instead \$\endgroup\$ – papagaga Aug 30 '18 at 15:26
  • 5
    \$\begingroup\$ @papagaga Improving algorithms is absolutely part of Code Review. That's what many of the algorithm and time-limit-exceeded questions are about. \$\endgroup\$ – 200_success Aug 30 '18 at 18:03
  • 1
    \$\begingroup\$ @papagaga Algorithms can always be improved—often immensely. As long as the code posted meets the requirements of the site, it's on-topic. All parts are considered reviewable, even if its a question that is masquerading as a code review for some other nefarious purpose. \$\endgroup\$ – Snowhawk Aug 30 '18 at 18:04
  • \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Mast Aug 31 '18 at 5:50
  • 2
    \$\begingroup\$ @Phoenix Which was pointed out in an answer. So if you remove them, that part of the answer makes no sense. That's answer invalidation. \$\endgroup\$ – Mast Aug 31 '18 at 7:08
9
\$\begingroup\$

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

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
\$\endgroup\$
6
\$\begingroup\$

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:

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

  2. 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.

  3. 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.

  4. 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;
}
\$\endgroup\$
  • \$\begingroup\$ @Deduplicator why did you change the code ? \$\endgroup\$ – Phoenix Aug 31 '18 at 13:17
  • 1
    \$\begingroup\$ The changed code dispenses with the lambda I needed earlier to avoid duplication, and it's shorter by 7 of 25 lines. Unfortunately boost::find_not never made it into the standard, or it would be even better. And I didn't want to include part of boost here just for that. \$\endgroup\$ – Deduplicator Aug 31 '18 at 14:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.