Longest word simple online challenge

Question

For lack of better things to do I went on coderbyte and did one of the simple challenges since I have not written code for a little while.

The problem was stated as following:

Have the function LongestWord(sen) take the sen parameter being passed and return the largest word in the string. If there are two or more words that are the same length, return the first word from the string with that length. Ignore punctuation and assume sen will not be empty.

Few notes to TL;DR the comments:

• I would have used const std::string& but function definition was given by CoderByte
• string[string.length()] is guaranteed to return '\0' since C++11.
• My code does not look for any terminating zeroes.

I'm looking for more discussion regarding the structure, the approach to the problem and general look & feel.

This is my solution:

// The function definition was given by CoderByte, I would have used     
// const std::string& if it was up to me
string LongestWord(string sen) { 
  // code goes here   
  int start = -1;
  int bstart = -1;
  int blen = 0;

  // lequal since std string is compatible with c strings, it will have \0 at 
  // the end, saving a special case after the loop.
  for (int i = 0; i <= sen.length(); ++i)
  {
      if (start == -1 && isalpha(sen[i]))
      {
          start = i;
      }
      else if (!isalpha(sen[i]))
      {
          if (start >= 0 && i - start > blen)
          {
               blen = i - start;
               bstart = start;
               start = -1;
          }
      }
  }

  return sen.substr(bstart, blen); 
}

I ran the test cases and all was well, so I figured I'd check the top solution on the website:

string LongestWord(string sen) { 

  // code goes here   
  string sen2 = "";
  for(int i=0;i<sen.length();i++)
  {
    if(isalpha(sen[i])||sen[i]==' '||'0'<=sen[i]&&sen[i]<='9')
    {
      sen2.append(sen.substr(i,1));
    }
  }
  char* sench = (char*)sen2.c_str();
  string longest = "";
  int longestLen = 0;
  for(const char* pch=strtok(sench," ");pch;pch=strtok(NULL," "))
  {
    if(strlen(pch)>longestLen)
    {
      longest = pch;
      longestLen=strlen(pch);
    }
  }
  return longest;         
}

From my point of view my solution is less complicated, has fewer moving parts, is easier to digest and at first glance I expect it to perform better due to less looping(although I have not tested this).

I feel like I am missing something, this happens with some frequency where I notice people use more complex solutions and I wonder if I'm basically writing tutorial code or something. Is this just me doubting myself or have I missed something?

Answer 1

Your solution is certainly neater than the other one. Programming challenge websites often contain horrible code.

There's a few things to improve though:

---

Use the container index type for indexing into a container. This ensures the index values cover the necessary range.

In this case, we should use std::size_t instead of int for indexing the std::string (or std::string::size_type if we're being paranoid). This would mean rethinking the algorithm slightly (perhaps we need a std::optional<std::size_t>).

Note that for storing the difference between indices (i.e. word length) we should use std::ptrdiff_t (or std::string::difference_type).

---

In C++ it's more idiomatic to use iterators, instead of indices. This makes it easier to genericize functions (e.g. finding the longest run satisfying an arbitrary precondition on an arbitrary sequence).

---

I'd be inclined to implement this with an outer loop to iterate each word, and an inner loop to find the start and end points.

It's more verbose, but perhaps a bit easier to follow:

#include <algorithm>
#include <cctype>
#include <string>

std::string get_longest_word(std::string const& input)
{
    auto const is_in_word = [] (unsigned char c) { return std::isalpha(c); };

    auto max_word_length = std::string::difference_type{ 0 };
    auto max_word_start = input.end();
    auto max_word_end = input.end();

    for (auto i = input.begin(); i != input.end(); )
    {
        auto word_start = std::find_if(i, input.end(), is_in_word);

        if (word_start == input.end())
            break;

        auto word_end = std::find_if_not(word_start, input.end(), is_in_word);

        auto const word_length = std::distance(word_start, word_end);

        if (word_length > max_word_length)
        {
            max_word_length = word_length;
            max_word_start = word_start;
            max_word_end = word_end;
        }

        i = word_end;
    }

    return std::string(max_word_start, max_word_end);
}

Which is on the way to becoming:

template<InputItT, PredicateT>
std::pair<InputItT, InputItT> find_longest_run(InputItT begin, InputItT end, PredicateT predicate);

Answer 2

The presented solution is quite C-like with strtok and such. For your solution:

• Your function takes the input by-value, but this seems unnecessary and wasteful. Prefer to take it by const-reference.

• The idea behind your solution looks OK, but you should notice that std::string can contain multiple null characters and is not null-terminated. In general, I would prefer to solve the problem by leveraging the standard library more. For example, we could write:

  #include <iostream>
  #include <string>
  #include <algorithm>
  #include <cctype>
  
  std::string LongestWord(const std::string& str)
  {
      std::string longest;
  
      for (auto first = str.cbegin(); first != str.cend(); )
      {
          auto w_end = std::adjacent_find(first, str.cend(),
              [](char a, char b)
          {
              return std::isalpha(static_cast<unsigned char>(a)) !=
                  std::isalpha(static_cast<unsigned char>(b));
          });
  
          if (w_end != str.cend())
          {
              ++w_end;
          }
  
          if(std::isalpha(static_cast<unsigned char>(*first)) && 
              std::distance(first, w_end) > longest.size())
          {
              longest = std::string(first, w_end);
          }
  
          first = w_end;
      }
  
      return longest;
  }
  
  int main()
  {
      std::string sen = "Some ,long sentence!!!!! with punctuation \t, and. all that!";
  
      const std::string w = LongestWord(sen);
      std::cout << w << "\n";
  }