How/Where can I optimize me code?

[Rodev]

Hello,

I am trying to code a class named longestConsec for an exercise at coding website.

So far my code (see below) passes the initial tests, but when I try to submit it for the random tests, after many seconds processing, the system gives me this message:
"Process was terminated. It took longer than 12000ms to complete"

Therefore, could anyone help me understand where/how I can optimize my code below?

THANKS! :)

Instructions for the exercise:

You are given an array strarr of strings and an integer k. Your task is to return the first longest string consisting of k consecutive strings taken in the array.

#Example: longest_consec(["zone", "abigail", "theta", "form", "libe", "zas", "theta", "abigail"], 2) --> "abigailtheta"

n being the length of the string array, if n = 0 or k > n or k <= 0 return "".

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

class LongestConsec
{
public:
    static bool compare (int i, int j)
    {
      return (i > j);
    }

    static std::string longestConsec(std::vector<std::string> &strarr, int k)
    {
      int strarr_size = strarr.size();

      std::vector<int>elem_size;

      // creates a vector of the elements' size
      for(auto s : strarr)
        elem_size.push_back(s.size());

      // sorts, excludes duplicates and leaves only k elements'sizes
      std::sort(elem_size.begin(), elem_size.end(), compare);
      std::vector<int>::iterator it;
      it = std::unique(elem_size.begin(), elem_size.end());
      elem_size.resize(std::distance(elem_size.begin(),it));
      elem_size.erase(elem_size.begin() + k, elem_size.end()); //leave only k elemnts

      std::vector<std::string> v_result;

      if (strarr_size == 0 || k > strarr_size || k <= 0)
      {
        return "";
      }
      else
      {
        for (auto j = 0; j != strarr_size; ++j)
        {
          for (auto i = 0; i != k; ++i)
          {
            if (elem_size[i] == strarr[j].size())
            {
              v_result.push_back(strarr[j]);
            }
          }
        }
      }

      v_result.erase(v_result.begin() + k, v_result.end());

      std::string result;

      for (auto v : v_result)
        result += v;

      std::cout << result << '\n'; //for testing only
      return result;
    }
};

:)

[jonnin]

did you compile it with optimizations on?

what does the triple loop do, can that be simplified?

if you do not need that explicit resize command, do not invoke it. Best: size the vectors big enough so they never need to resize , or infrequently resize, up front.

[JLBorges]

It can be done in O(n) with a variant of Kadane's algorithm (one pass through the array)
https://en.wikipedia.org/wiki/Maximum_subarray_problem#Kadane.27s_algorithm

Something like this:

#include <iostream>
#include <string>
#include <numeric>

std::string max_sub_array_k( const std::string strarr[], std::size_t n, std::size_t k )
{
    if( !strarr || n < k || k == 0 ) return {} ;

    std::size_t curr_sum = 0 ; // sum of lengths of the first k strings
    for( std::size_t i = 0 ; i < k ; ++i ) curr_sum += strarr[i].size() ;

    std::size_t max_so_far = curr_sum; // initially sum of lengths of k strings fstarting at  0
    std::size_t pos_max_so_far = 0 ; // start position of the max sum subsequence

    for( std::size_t i = k ; i < n ; ++i )
    {
        // moving window: add the length of the new string, subtract the length of the oldest string,
        curr_sum += strarr[i].size() - strarr[i-k].size() ;

        if( curr_sum > max_so_far )
        {
            max_so_far = curr_sum ;
            pos_max_so_far = i-k+1 ;
        }
    }

    return std::accumulate( strarr+pos_max_so_far, strarr+pos_max_so_far+k, std::string{} ) ;
}

int main()
{
    const std::string strarr[] = { "zone", "abigail", "theta", "form", "libe", "zas", "theta", "abigail" } ;
    const std::size_t n = sizeof(strarr) / sizeof( strarr[0] ) ;

    const std::size_t k = 2 ;
    std::cout << max_sub_array_k( strarr, n, k ) << '\n' ;
}

http://coliru.stacked-crooked.com/a/462d0ccc824a2554

[Enoizat]

Hope this alternative version could be of any inspiration.
Remove all comments and the following lines:

#include <limits>
. . .
void waitForEnter();
. . .
    waitForEnter();
. . .
void waitForEnter()
{
    std::cout << "\nPress ENTER to continue...\n";
    std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
}

to make it even shorter (they just keep the console window open).

// Instructions for the exercise:
// You are given an array strarr of strings and an integer k. Your task is to 
// return the first longest string consisting of k consecutive strings taken 
// in the array.
// #Example: longest_consec(["zone", "abigail", "theta", "form", "libe", 
// "zas", "theta", "abigail"], 2) --> "abigailtheta"
// n being the length of the string array, if n = 0 or k > n or k <= 0 return "".
#include <iostream>
#include <limits>
#include <string>
#include <vector>

std::string longestConsec(const std::vector<std::string>& strarr, int k);
void waitForEnter();

int main()
{
    std::vector<std::string> vecstr { "zone", "abigail", "theta", "form", 
                                      "libe", "zas", "theta", "abigail" };
    int consec = 2;
    std::cout << "longest sequence: " << longestConsec(vecstr, consec) << '\n';
    waitForEnter();
    return 0;   
}

std::string longestConsec(const std::vector<std::string>& strarr, int k)
{
    if(strarr.empty() || k > strarr.size() || k<= 0) { return ""; }
    int longest {}, position {};
    for(int i {}; i<strarr.size()-k; ++i) {
        int total {};
        for(int j{i}; j<k+i; ++j) { total += strarr.at(j).length(); }
        if(longest < total) {
            longest = total;
            position = i;
        }
    }
    std::string melt;
    for(int i{position}; i<k+position; ++i) { melt += strarr.at(i); }
    return melt;
}

void waitForEnter()
{
    std::cout << "\nPress ENTER to continue...\n";
    std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
}