LeetCode 58: Length of Last Word

Problem Restatement

We are given a string s containing English letters and spaces.

We need to return the length of the last word in the string.

A word is a maximal substring made only of non-space characters. The string contains at least one word. The official constraints are 1 <= s.length <= 10^4, and s contains only English letters and spaces.

Input and Output

Function shape:

def lengthOfLastWord(s: str) -> int:
    ...

Examples

For:

s = "Hello World"

The last word is:

World

Its length is:

5

So the answer is:

5

For:

s = "   fly me   to   the moon  "

The trailing spaces do not count.

The last word is:

moon

The answer is:

4

For:

s = "luffy is still joyboy"

The last word is:

joyboy

The answer is:

6

First Thought: Split the String

A simple solution is to split the string into words and return the length of the last word.

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

This works because Python’s split() without arguments ignores extra spaces.

For example:

"   fly me   to   the moon  ".split()

produces:

["fly", "me", "to", "the", "moon"]

Then the last word is easy to read.

Problem With Split

The split solution is valid, but it creates a list of all words.

We only need the last word. Building every word uses extra memory.

A direct scan from the end avoids that extra allocation.

Key Insight

The last word is closest to the end of the string, but there may be spaces after it.

So we scan from right to left:

1. Skip trailing spaces.
2. Count non-space characters.
3. Stop when we reach a space before the last word.

This reads only what is necessary.

Algorithm

Start from the last index:

i = len(s) - 1

First, skip spaces at the end:

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

Then count the last word:

length = 0

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

Return length.

Correctness

After the first loop, i points to the last non-space character in the string. Since the input contains at least one word, such a character exists.

The second loop moves left while the current character belongs to the last word. It increments length once for each character in that word.

The loop stops when it reaches either the beginning of the string or the space before the last word. Therefore length equals exactly the number of characters in the last word.

Complexity

Implementation

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

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

        length = 0

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

        return length

Code Explanation

We begin at the final character:

i = len(s) - 1

The first loop skips spaces after the last word:

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

Now i is at the last character of the last word.

Then we count characters until we hit a space:

length = 0

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

Finally, return the count:

return length

Testing

def run_tests():
    s = Solution()

    assert s.lengthOfLastWord("Hello World") == 5
    assert s.lengthOfLastWord("   fly me   to   the moon  ") == 4
    assert s.lengthOfLastWord("luffy is still joyboy") == 6
    assert s.lengthOfLastWord("a") == 1
    assert s.lengthOfLastWord("a ") == 1
    assert s.lengthOfLastWord("single") == 6
    assert s.lengthOfLastWord("many   spaces") == 6

    print("all tests passed")

run_tests()