Finding the Longest Word in a String

Question

Challenge:

Return the length of the longest word in the provided sentence.

I've made a solution that works but it is kinda bad since the time complexity is \$O(n \log n)\$ and it involves mutation.

function findLongestWordLength(str) {
 let strSplit = str.split(" ");
 let wordLengthArray = [];
 for(let i = 0; i < strSplit.length; i++)
 {
 wordLengthArray.push(strSplit[i].length);
 }
 wordLengthArray.sort(function(a , b){return a - b});
 return wordLengthArray[wordLengthArray.length - 1];
}

I basically split the string, pushed all the word lengths in an empty array, then used the ascending sort function. After that I returned the last index of the new array which is the longest length.

Test Cases:

findLongestWordLength("The quick brown fox jumped over the lazy dog") should return 6.
findLongestWordLength("May the force be with you") should return 5.
findLongestWordLength("Google do a barrel roll") should return 6.
findLongestWordLength("What is the average airspeed velocity of an unladen swallow") should return 8.
findLongestWordLength("What if we try a super-long word such as otorhinolaryngology") should return 19.

I would appreciate some hints/tips on a better algorithm.

Answer 1

You are creating an array of strings (using str.split(" ")) as well as an array of numbers (wordLengthArray), then sorting wordLengthArray. All three of those operations are wasteful, if you are aiming for performance.

function findLongestWordLength(str) {
 let maxLen = -1;
 for (var i = 0, j; (j = str.indexOf(" ", i)) != -1; i = j + 1) {
 maxLen = Math.max(maxLen, j - i);
 }
 return Math.max(maxLen, str.length - i);
}
console.log(6 == findLongestWordLength("The quick brown fox jumped over the lazy dog"));
console.log(5 == findLongestWordLength("May the force be with you"));
console.log(6 == findLongestWordLength("Google do a barrel roll"));
console.log(8 == findLongestWordLength("What is the average airspeed velocity of an unladen swallow"));
console.log(19 == findLongestWordLength("What if we try a super-long word such as otorhinolaryngology"));

Depending on the browser/interpreter, your function is 33% to 86% slower than mine.

Answer 2

What I'm seeing is that you touch the data twice. This isn't necessary for retrieving a simple fact about the data.

Consider, saving the length of each word and comparing lengths as you go along. Even with a perfectly linear sort function (That is, O(n-1)) this will still cut down on algorithm complexity, simply because you aren't calling a sort function at all.

EDIT: I had a variable saving the word as well as the length, but after reading over your question again, I found that that isn't what you were looking for. EDIT2: I removed my code because you said you wanted HINTs. sorry...

Answer 3

Thanks to @Kruga, here is a javascript implementation of my original pseudo code which gives the answer in a single pass. No splits, no arrays, no sorting:

function findLongestWordLength(str) {
 let currentCount = 0;
 let currentMax = 0;
 for(let char of str) {
 if(char != " ") {
 currentCount += 1;
 }
 else {
 if(currentCount > currentMax) currentMax = currentCount;
 currentCount = 0;
 }
 }
 if(currentCount > currentMax) currentMax = currentCount; // take care of last word
 return currentMax;
}

• Kruga: Here is the code written in javascript

Answer 4

This is like getting biggest number algorithm.

const text = 'The quick brown fox jumped over the lazy dog';
const longWord = n => {
 let arr = n.split(' ');
 let longestWordCount = arr[0];
 arr.forEach(element => {
 if (element.length > longestWordCount.length) {
 longestWordCount = element;
 }
 });
 console.log(longestWordCount.length);
}
longWord(text);