5
\$\begingroup\$

Write a function called longest which will take a string of space-separated words and will return the longest one.

My code:

function longest(str) {
  var words = arguments.split(" ");
  var words_count = words.length;

  var longest_word_length = 0;

 for(var i = 0; i < words_count; i++){
   if(longest_word_length < words[i].length){
       longest_word_length = words[i].length;
   }
}
return longest_word_length;
}

Running it with this test:

describe("test for longest function functionality", function() {
  it("should return correct output for normal strings", function() {
  expect(longest("A")).toEqual("A");
  expect(longest("I love Avatar")).toEqual("Avatar");
  expect(longest("The stupidities of youth")).toEqual("stupidities");
  });

  it("should return correct output for gibberish", function() {
  expect(longest("hgdydrxtfEq Rradsc tstsa taeWwwecfgdd")).toEqual("hgdydrxtfEq");
  });

 it("should work for sentences with numbers", function() {
 expect(longest("This is a sentence with a number 7685838788")).toEqual("7685838788");
 });
});
\$\endgroup\$
8
  • 3
    \$\begingroup\$ Just to note, your code should be failing your tests. The longest word is not equal to the length of the longest word. \$\endgroup\$
    – cHao
    Commented Apr 14, 2017 at 19:45
  • 1
    \$\begingroup\$ Four answers and no one has mentioned that str is ignored and the array of arguments is split instead which obviously fails. :p \$\endgroup\$ Commented Apr 14, 2017 at 22:01
  • \$\begingroup\$ Related. \$\endgroup\$ Commented Apr 14, 2017 at 22:41
  • \$\begingroup\$ As we now have two users asking the same question with exactly the same flawed code & test cases - where does this problem originate from? \$\endgroup\$
    – le_m
    Commented Apr 15, 2017 at 0:15
  • \$\begingroup\$ @le_m Are you referring to the 2.5 year question that insertusernamehere linked to? Because that contains very different code. And I don't see what's flawed about the test cases here? \$\endgroup\$
    – Flambino
    Commented Apr 15, 2017 at 0:22

4 Answers 4

12
\$\begingroup\$

Good on you for writing real tests.

Overall, the code seems fine as-is (edit: Actually, no. See David Harkness' comment on the question; arguments.split should be str.split) though I do have a few comments:

  • The JavaScript convention is to use camelCase for variable names - not snake_case.

  • Splitting by " " works, but a more comprehensive solution would be to split by /\s+/. That is, split by one or more whitespace characters. That way you avoid zero-length strings in the array if there are two spaces in a row, and it'll also split on newlines and other whitespace. And if you trim() the string first, you'll also avoid empty strings at the start/end if the input string has leading or trailing whitespace.

Also the whole thing can be made more functional (and use some ES6 syntax):

function longest(string) {
  return string
    .trim()
    .split(/\s+/)
    .reduce((longest, word) => word.length > longest.length ? word : longest);
}

reduce (aka "fold" in other languages), when given no 2nd argument, will use the first element - the first word - in the array as its initial memo. The callback then either reuses that word, or replaces it when it finds one that's longer. Whatever the memo is at the end is what gets returned.


Another approach, much less functional, could be to use String.replace as a "scan" function:

function longest(string) {
  var length = 0;
  var longestWord = "";
  string.replace(/\S+/g, (word) => {
    if(word.length > length) {
      length = word.length;
      longestWord = word;
    }
    return ""; // for good measure; otherwise all words will be replaced with "undefined" in-memory
  });
  return longestWord;
}

The regex finds any run of non-whitespace character of length 1 or more. It's not terribly pretty, since replace isn't being used "as intended", really, and there are some closure side-effects. It doesn't have the memory consumption of the previous solution however (no array used to hold the split string).

\$\endgroup\$
4
  • \$\begingroup\$ Instead of the hackish replace, could regex.scan do the trick? \$\endgroup\$
    – le_m
    Commented Apr 15, 2017 at 0:12
  • \$\begingroup\$ @le_m there is no such method in JS's RegExp unfortunately. You can do the same thing with repeated calls to exec (MDN has an example), but frankly I find it more cumbersome than (mis-)using replace which lets you do things with a callback \$\endgroup\$
    – Flambino
    Commented Apr 15, 2017 at 0:18
  • \$\begingroup\$ exec is what I meant, my bad. You are right, looks a bit unreadable. Will remove my comments. \$\endgroup\$
    – le_m
    Commented Apr 15, 2017 at 0:22
  • \$\begingroup\$ @le_m Nah, leave it - it's a valid solution and a good comment \$\endgroup\$
    – Flambino
    Commented Apr 15, 2017 at 0:22
3
\$\begingroup\$

Your implementation has two flaws; you do not search the input argument str but the arguments array and you return the length of the longest word rather that the longest word itself. Assuming these two errors are fixed, the following improvements can be made:

Performance optimizations: In case you wish to improve performance, I suggest avoiding the creation of a temporary array holding individual words and instead iterate over the input string and looking for space characters via string.indexOf():

// Return longest word in 'string':
function longest(string) {
  let length = 0, start = 0, last, next = -1;
  
  do {
    last = next + 1;
    next = string.indexOf(" ", last);
    
    if (next - last > length) {
      length = next - last;
      start = last;
    }
  } while (next > -1)
  
  if (string.length - last > length) {
    length = string.length - last;
    start = last;
  }
    
  return string.substring(start, start + length);
}

// Example:
console.log(longest("a ab abc"));

This approach has turned out to be very fast according to https://jsperf.com/longest-word-in-string-4. You might want to experiment with increasing the step-size by the length of the currently found longest word and looking back for the next space in order to find a longer word than currently found. However, this would require more complex inner loop logic which might perform poorly and thus requires profiling on your targeted JavaScript engines.

Micro-optimizations: By assigning var words_count = words.length followed by for (var i = 0; i < words_count; i++) you perform an assumed micro-optimization which I would either remove or - if performance is key and you don't trust your favorite JavaScript engine's hotspot optimization - replace with the often encountered for (var i = 0, length = words.length; i < length; ++i) or for (var i = words.length - 1; i >= 0; --i) after profiling the code on your desired platform.

Also consider the modern and more descriptive for-of loop as in for (let word of words).

Declarative vs. descriptive: If desired, it is possible to convert your declarative code to a more descriptive style by using the functional style array.reduce function:

// Return longest word in 'string':
function longest(string) {
  let words = string.split(" ");
  return words.reduce((prev, next) => prev.length > next.length ? prev : next);
}

// Example:
console.log(longest("a ab abc")); // "abc"

Also see @Flambino's answer. This approach has turned out to be of similar performance compared to your implementation according to https://jsperf.com/longest-word-in-string-4.

Naming convention: While JavaScript generally follows the camelCase instead of under_score naming convention, it is really up to your environment and your local guidelines.

\$\endgroup\$
3
  • \$\begingroup\$ This returns the length of the longest word, not the word itself, as the tests expect \$\endgroup\$
    – Flambino
    Commented Apr 14, 2017 at 17:16
  • \$\begingroup\$ @Flambino that's... stupid. I'll fix it, thanks for pointing it out. \$\endgroup\$
    – le_m
    Commented Apr 14, 2017 at 17:40
  • \$\begingroup\$ heh, no prob. Otherwise a nice solution with map + spread operator \$\endgroup\$
    – Flambino
    Commented Apr 14, 2017 at 17:41
2
\$\begingroup\$

I completely agree with what user24119 said above. I don't know how quickly or slowly Javascript's String.split method works but this will achieve the same result in O(n) time with O(1) memory:

var input = "find the LONGEST str in here";

function longest(str) {
  var longestStart = 0;
  var longestEnd = 0;
  var current = 0;
  var currentLength = 0;
  while (current < str.length) {
    if (str.charAt(current) == ' ') {
      if (currentLength > (longestEnd - longestStart)) {
        longestStart = (current - currentLength);
        longestEnd = current;
      }
      currentLength = 0;
    } else {
      currentLength++;
    }
    current++;
  }
  return str.substring(longestStart, longestEnd);
}

alert(longest(input));
\$\endgroup\$
1
  • \$\begingroup\$ If n = number of characters, then you are still within O(n) space complexity - e.g. for input "thisisalonglongsinglewordstring". If n = number of words, then you are right, but that would be a strange choice as above single word string would then compute in O(1). \$\endgroup\$
    – le_m
    Commented Apr 14, 2017 at 22:53
1
\$\begingroup\$

Being old-school I would prefer another approach. I am used to programming where both CPU time and memory are constraints.

Splitting the string will duplicate it, doubling the memory usage. You also need to run through the entire string twice; once to split it, and then through all the substrings to find the longest one.

By testing the string in-place, I can find the longest word in only one pass, without duplicating it.

set 'startOfWordPointer' to start of string;
set 'endOfWordPointer' to 'startOfWordPointer' and increase, till you find a split-character (like space-tab-period etc).

The Word is now defined as between wordpointer and endOfWordPointer
Have you found the longest word so far?  
Then remember it.

Then set 'startOfWordPointer' to 'EndOfWordPointer'.
Increase startOfWordPointer as long as you find split-characters.

After that, 'startOfWordPointer' is pointing to the next word. 
Rinse and repeat.
  • One pass
  • Memory requirements only 4 integers / pointers (2 for pointers, 2 to remember the longest word found so far)

Arguably, splitting could be made more efficient, by only pointing to the original string. The string would not be copied. Calculating the length would not require to run over the string but could be derived from the pointers. I'm not sure if splitters are that efficient, though.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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