LeetCode 58 – Length of Last Word

Length of Last Word is a warm-up, and it is on the list precisely because it is one. Easy problems are where interviewers watch how you write rather than whether you can — and this one has a one-liner that is correct, wasteful, and the answer most people give.

The problem

Given a string of words separated by spaces, return the length of the last word. A word is a maximal substring of non-space characters. The string may have trailing spaces, and is guaranteed to contain at least one word.

"Hello World"                -> 5
"   fly me   to   the moon  " -> 4     trailing spaces, and runs of them
"luffy is still joyboy"      -> 6
"a"                          -> 1
"a "                         -> 1
"day"                        -> 3

Everything interesting is in example 2. Trailing spaces are why the naive lastIndexOf(' ') answer returns 0, and runs of spaces between words are why splitting on a single space produces empty strings.

The one-liner, and why it is the wrong answer

class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        return len(s.split()[-1])

Correct. split() with no argument splits on runs of whitespace and discards empties, so the trailing spaces and double spaces are both handled. And to read one word it allocates a list of every word in the string, which for a one-megabyte input with a three-letter last word is a lot of garbage produced in order to be ignored.

Java's s.trim().split(" ") is worse: it allocates a trimmed copy and the array, and split(" ") on a single literal space leaves empty strings in the middle for runs of spaces. It still happens to work here — the last element is never empty after trimming — but it works by luck.

Say the one-liner, note it is O(n) extra space, then write the real one. That sequence is the answer; either half alone is not.

Scan backwards

You want the last word, so start at the end. Two loops, no allocation:

"   fly me   to   the moon  "
                            ^ i starts here

skip trailing spaces  ->  i lands on 'n', remember it as `end`
walk back over letters -> i lands on the space before 'moon'

length = end - i        = 24 - 20 = 4

The subtraction is the part to get right, and the reason it works without a + 1 is that i stops one before the word — on the space, or at -1 when the word runs to the start of the string. Both cases give the same arithmetic, which is why there is no special case for "the string is a single word".

Java

class Solution {
    public int lengthOfLastWord(String s) {
        int i = s.length() - 1;

        while (i >= 0 && s.charAt(i) == ' ') {   // skip the trailing spaces
            i--;
        }

        int end = i;                              // last character of the last word
        while (i >= 0 && s.charAt(i) != ' ') {   // walk back over the word itself
            i--;
        }

        return end - i;      // i sits on the space before the word, or at -1
    }
}

The i >= 0 guard in the second loop is what handles "a" and "day", where there is no space to stop at. Dropping it gives a StringIndexOutOfBoundsException on exactly the inputs a quick mental test does not cover.

Python

class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        i = len(s) - 1

        while i >= 0 and s[i] == " ":
            i -= 1

        end = i
        while i >= 0 and s[i] != " ":
            i -= 1

        return end - i

Python's negative indexing makes the guards matter more, not less: without i >= 0 the loop does not crash at i = -1, it wraps around to the end of the string and keeps going. A missing bounds check that raises is a bug you find in one run; one that silently reads the wrong data is a bug you find in production.

Complexity

The backward scan is the only one that does not read the whole string. On "…a million characters… hello " it touches about eight of them. Worst case is still O(n) — a string that is one long word — but the typical case is genuinely better, and noticing that the input does not need to be fully read is the kind of observation that separates answers on an easy problem.

The middle-ground answer

If you want one line in Java that is still O(n) but at least honest about it:

        String t = s.trim();
        return t.length() - t.lastIndexOf(' ') - 1;

lastIndexOf returns -1 when there is no space, which gives length - (-1) - 1 = length — the single-word case falls out correctly with no branch. That is a nice property and worth pointing out; it is still a full trimmed copy of the string for one integer.

What the interviewer is checking

• Trailing spaces — the case that breaks the first thing most people write.
• Runs of spaces between words.
• That you scan from the end rather than parsing the whole string.
• The i >= 0 guards, especially the second one.
• That end - i needs no + 1, and that you can say why.
• That you name the built-in solution and then explain the trade-off you are making instead of pretending not to know it.
• A single-character string, and a string that is one word with no spaces at all.