Length of Last Word
Understanding the Problem
We need the length of the last word in a string. The complication is trailing spaces. "Hello World " has the last word "World" (length 5), so the trailing spaces must be skipped before counting.
The task reduces to: skip any trailing spaces, then count characters backward until reaching another space or the beginning of the string. That count is the answer.
Key Constraints:
1 <= s.length <= 10^4→ A single linear pass is more than fast enough, and the problem has clean O(n) solutions.sconsists of only English letters and spaces → No tabs or newlines to handle, so the only delimiter is a single space character.- There is at least one word in
s→ A valid answer always exists, so there is no empty-input case to guard against.
Approach 1: Split and Find Last Word
Intuition
Split the string into words and take the last one. Its length is the answer.
The detail that matters is how the split treats spaces. A naive split(" ") produces empty strings wherever two spaces sit next to each other or at the ends. The fix is to use a whitespace-aware splitter that collapses runs of spaces and drops the empty pieces (Python's str.split() with no argument, Go's strings.Fields), or to filter the empty strings out after splitting on a single space. Either way, the result is a clean list of words, and the last element is the last word.
Algorithm
- Split
son whitespace, collapsing runs of spaces so no empty strings remain. - Take the last element of the resulting list.
- Return its length.
Example Walkthrough
Input:
After splitting: words = ["fly", "me", "to", "the", "moon"]
Last word is "moon", length = 4:
Code
- Time Complexity: O(n). The split scans every character, even though only the last word is needed.
- Space Complexity: O(n). The split allocates a list of all words, which in the worst case holds every character.
This is correct, but it scans the whole string and allocates a list of every word to use only the last one. The next approach removes both costs by working backward from the end.
Approach 2: Traverse from End (Optimal)
Intuition
The last word sits at the end of the string, so scan backward from the last index. First decrement past any trailing spaces. Then count non-space characters until reaching a space or the start of the string. That count is the answer.
This reads only as many characters as needed. For "Hello World", it touches the last 5 characters plus any trailing spaces and never looks at the rest. It also uses no extra storage, so the space cost drops to O(1).
The i >= 0 check in both loops is what keeps the scan safe. After the first loop, i points at the last non-space character (or is -1 if the string was all spaces, which the constraints rule out). The second loop stops either at a space separating the last word from the previous one or at i = -1 when the last word starts at index 0, as in "day". Both cases return the correct count without an out-of-bounds access.
Algorithm
- Start from the last index of the string.
- Skip all trailing spaces by decrementing the index while the current character is a space.
- Count non-space characters by decrementing the index while the current character is not a space.
- Return the count.
Example Walkthrough
Code
- Time Complexity: O(n). In the worst case (a single word with no trailing spaces), we scan the entire string. On average, we only scan the trailing spaces plus the last word.
- Space Complexity: O(1). Only two integer variables (
iandlength). No extra data structures.