Skip to main content
CodePeet

Longest Word in a Sentence

Try it yourself
EasyProblem

Description

Given a sentence s, return its longest word. A word is a run of characters that aren't spaces, and words are separated by one or more spaces. If several words are equally long, return the first of them.

Examples

Example 1

Input: s = "I love programming"

Output: "programming"

Explanation: programming has 11 characters, more than I or love.

Example 2

Input: s = "an at in"

Output: "an"

Explanation: All three have 2 letters; the first of them, an, is the answer.

Example 3

Input: s = " hello "

Output: "hello"

Explanation: The spaces around it don't belong to the word.

Example 4

Input: s = "a bb ccc dd"

Output: "ccc"

Explanation: ccc, with 3 characters, is the longest.

Constraints

  • 1 ≤ s.length ≤ 10^5
  • s consists of English letters, digits, punctuation and spaces (' ')
  • s has at least one word

Editorial

Approach - Measure Each Word as It Ends

Intuition

A word ends at the first space after it, or at the end of the string. When one ends, compare its length with the best so far, and keep it only if it's strictly longer: then of several equally long words the first one stays, as the problem asks.

Don't forget the last word: often no space comes after it, so the end of the string has to end a word too.

Step-by-Step Explanation

Let's trace Example 2, s = "an at in":

  1. an, 2 characters: longer than anything before, so it's the best.
  2. at, 2 characters: not longer than an, so an stays.
  3. in, 2 characters: not longer than an, so an stays.
  4. Return "an".

The First Longest Word — The best word so far in green; a word that's only as long, in amber, doesn't replace it.

Algorithm

  1. Keep the best word, empty at first, and where the current word started.
  2. At each space, and once more at the end of the string: if a word just ended and it's longer than the best, it becomes the best.
  3. Return the best.

Code

class Solution {
public:
    string longestWord(string& s) {
        string best;
        int start = -1, n = s.size();
        for (int i = 0; i <= n; i++) {
            if (i < n && s[i] != ' ') {
                if (start < 0) start = i;   // a word begins
            } else if (start >= 0) {        // a word just ended, at a space or the end
                if (i - start > (int) best.size()) best = s.substr(start, i - start);
                start = -1;
            }
        }
        return best;
    }
};

class Solution:
    def longestWord(self, s: str) -> str:
        best, start = "", -1
        for i in range(len(s) + 1):
            if i < len(s) and s[i] != " ":
                if start < 0:
                    start = i               # a word begins
            elif start >= 0:                # a word just ended, at a space or the end
                if i - start > len(best):
                    best = s[start:i]
                start = -1
        return best

class Solution {
    public String longestWord(String s) {
        String best = "";
        int start = -1;
        for (int i = 0; i <= s.length(); i++) {
            if (i < s.length() && s.charAt(i) != ' ') {
                if (start < 0) start = i;   // a word begins
            } else if (start >= 0) {        // a word just ended, at a space or the end
                if (i - start > best.length()) best = s.substring(start, i);
                start = -1;
            }
        }
        return best;
    }
}

var longestWord = function(s) {
    let best = "", start = -1;
    for (let i = 0; i <= s.length; i++) {
        if (i < s.length && s[i] !== " ") {
            if (start < 0) start = i;       // a word begins
        } else if (start >= 0) {            // a word just ended, at a space or the end
            if (i - start > best.length) best = s.slice(start, i);
            start = -1;
        }
    }
    return best;
};

Complexity Analysis

Time Complexity: O(n)

Each character is looked at once, and each word copied at most once when it's the best.

Space Complexity: O(n)

The best word.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Replacing the best on a tie. len(word) >= len(best)

On s = "an at in" it returns "in"; the answer is "an". With >=, a later word of the same length replaces the best, so a tie gives the last of the longest words. Only a strictly longer word should replace it.

Only measuring a word at a space. for i in range(len(s)):

On s = "I love programming" it returns "love"; the answer is "programming". Measuring each word when a space ends it misses the last word if no space comes after it, and that may be the longest. The end of the string ends a word too.

Taking the space after the word. s[start:i + 1]

On s = "an at in" it returns "an "; the answer is "an". The word runs from its first character up to, not including, the space that ends it. Slicing to i + 1 takes that space along.

Where This Pattern Is Taught

This problem practises finding where each word starts and ends in one pass. It's taught in Introduction to Strings.