Problem Description

You are given a string s that contains words separated by spaces. Your task is to find and return the length of the last word in the string.

A word is defined as a continuous sequence of non-space characters. The string may have trailing spaces after the last word, which should be ignored when determining the last word.

For example:

• If s = "Hello World", the last word is "World" with length 5
• If s = " fly me to the moon ", the last word is "moon" with length 4 (trailing spaces are ignored)
• If s = "luffy is still joyboy", the last word is "joyboy" with length 6

The solution works by traversing the string from right to left. First, it skips any trailing spaces by moving the pointer i backwards until it finds a non-space character. This marks the end of the last word. Then it continues moving backwards with pointer j until it finds a space or reaches the beginning of the string. The difference i - j gives us the length of the last word.

Intuition

When we need to find the last word in a string, the most natural approach is to start from the end rather than the beginning. Why? Because if we start from the beginning, we'd have to traverse through all the words to reach the last one, which is unnecessary work.

Think about how you would manually find the last word if someone showed you a sentence on paper. You'd likely look at the end of the sentence and work backwards until you identify where the last word starts and ends.

The key insight is that we need to handle two scenarios:

1. There might be trailing spaces after the last word (like "hello world ")
2. The last word ends exactly at the last character (like "hello world")

So our strategy becomes:

1. Start from the very end of the string and skip any trailing spaces by moving backwards
2. Once we hit the first non-space character, we know we've found the end of the last word
3. Continue moving backwards from this position until we either hit a space (which marks the beginning of the last word) or reach the start of the string

Using two pointers (i and j) to mark these positions allows us to calculate the length simply as the difference between them. This approach is efficient because we only examine the characters we need to - we don't waste time processing the entire string when we only care about the last word.

Solution Approach

The solution implements a reverse traversal with two pointers to efficiently find the length of the last word.

Step-by-step implementation:

1. Initialize the first pointer i: Start from the last index of the string (len(s) - 1)

2. Skip trailing spaces:

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

   This loop moves i backwards as long as we encounter spaces. When this loop ends, i points to the last non-space character (the end of the last word).

3. Mark the end position: Store the current position of i in pointer j:

   j = i

4. Find the beginning of the last word:

   while j >= 0 and s[j] != ' ':
       j -= 1

   Continue moving j backwards as long as we encounter non-space characters. When this loop ends, j will be at position -1 if the last word starts at index 0, or it will point to the space character just before the last word.

5. Calculate the length:

   return i - j

   The length of the last word is the difference between i (end of last word) and j (position before the start of last word).

Example walkthrough with s = " hello world ":

• Initial: i = 13 (last index)
• After skipping trailing spaces: i = 11 (at 'd')
• Set j = 11
• After finding word beginning: j = 5 (at the space before 'world')
• Length = 11 - 5 = 6 (length of "world")

This approach has a time complexity of O(n) in the worst case where n is the length of the string, and space complexity of O(1) as we only use two pointer variables.

Example Walkthrough

Let's trace through the solution with s = " fly me ":

Initial state:

• String: " fly me " (indices 0-9)
• i = 9 (pointing to the last character, which is a space)

Step 1: Skip trailing spaces

• i = 9: s[9] = ' ' → move left
• i = 8: s[8] = ' ' → move left
• i = 7: s[7] = 'e' → stop (found non-space)

Step 2: Mark the end of last word

• Set j = i = 7

Step 3: Find the beginning of last word

• j = 7: s[7] = 'e' → move left
• j = 6: s[6] = 'm' → move left
• j = 5: s[5] = ' ' → stop (found space)

Step 4: Calculate length

• Length = i - j = 7 - 5 = 2
• The last word "me" has length 2 ✓

Visual representation:

Index:  0 1 2 3 4 5 6 7 8 9
String: _ _ f l y _ m e _ _
                  ^ ^     ^
                  j i   start

The algorithm correctly identifies "me" as the last word by working backwards from the end, skipping the trailing spaces, and finding where the word begins.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string s. In the worst case, the algorithm needs to traverse the entire string from the end to the beginning. The first while loop skips trailing spaces, and the second while loop counts the characters of the last word. Together, each character is visited at most once, resulting in linear time complexity.

The space complexity is O(1). The algorithm only uses two integer variables i and j to track positions in the string, regardless of the input size. No additional data structures are created that scale with the input, making the space usage constant.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not handling edge cases with only spaces

A common mistake is not properly handling strings that contain only spaces. If the input is " ", the algorithm might return an incorrect value or fail to handle the case where no word exists.

Problem scenario:

s = "     "  # String with only spaces

After skipping trailing spaces, end_index becomes -1, and if we don't check this condition, accessing s[end_index] in subsequent operations could cause issues.

Solution: Add a check after skipping trailing spaces to handle the case where no word exists:

def lengthOfLastWord(self, s: str) -> int:
    end_index = len(s) - 1
  
    # Skip trailing spaces
    while end_index >= 0 and s[end_index] == ' ':
        end_index -= 1
  
    # Check if the string contains no words (only spaces)
    if end_index < 0:
        return 0
  
    # Continue with finding the word beginning...
    start_index = end_index
    while start_index >= 0 and s[start_index] != ' ':
        start_index -= 1
  
    return end_index - start_index

2. Confusion between pointer positions and actual indices

Developers often get confused about what start_index represents after the second while loop. After finding the beginning of the word, start_index points to either:

• The space character just before the last word, OR
• -1 if the last word starts at index 0

Common mistake:

# Incorrect: trying to use start_index + 1 as the beginning
return end_index - (start_index + 1) + 1  # Overcomplicating

Correct understanding: The length calculation end_index - start_index works because:

• If start_index = -1: length = end_index - (-1) = end_index + 1 (correct for 0-indexed position)
• If start_index = k (space at position k): length = end_index - k (correct distance)

3. Using built-in methods incorrectly as an alternative

While the two-pointer approach is efficient, some might try to use built-in string methods but implement them incorrectly:

Incorrect approach:

def lengthOfLastWord(self, s: str) -> int:
    return len(s.split()[-1])  # Fails on empty string

Better alternative with built-in methods:

def lengthOfLastWord(self, s: str) -> int:
    words = s.strip().split()
    return len(words[-1]) if words else 0

The manual two-pointer approach is still preferred in interviews as it demonstrates understanding of string manipulation and edge case handling without relying on language-specific features.