Length of Last Word

• Difficulty: Easy
• Topics: String
• Link: https://leetcode.com/problems/length-of-last-word/

Problem Description

Given a string s consisting of words and spaces, return the length of the last word in the string.

A word is a maximal substring consisting of non-space characters only.

Example 1:

Input: s = "Hello World"
Output: 5
Explanation: The last word is "World" with length 5.

Example 2:

Input: s = "   fly me   to   the moon  "
Output: 4
Explanation: The last word is "moon" with length 4.

Example 3:

Input: s = "luffy is still joyboy"
Output: 6
Explanation: The last word is "joyboy" with length 6.

Constraints:

• 1 <= s.length <= 104
• s consists of only English letters and spaces ' '.
• There will be at least one word in s.

Solution

1. Problem Deconstruction

Technical Restatement
Given a string s of length n where 1 ≤ n ≤ 10⁴, with characters from the set {English letters, space}, return the length of the maximal contiguous substring of non-space characters that appears last in the string. Formally:
Let W = {w | w is a contiguous substring of s ∧ ∀c ∈ w, c ≠ ' '}
Return max_{w ∈ W} {len(w)} where the maximum is taken over the rightmost occurrence.

Beginner Explanation
We have a sentence (or phrase) where words are separated by spaces. Some spaces might be at the start or end. We need to find the last actual word (group of letters) in the sentence and count how many letters it has. For example, in “Hello World”, the last word is “World” which has 5 letters.

Mathematical Formulation
Let s[0..n-1] be the string. Define:

• is_alpha(c) = 1 if c is English letter, else 0
• word_end(i) = max{j | j ≤ i ∧ is_alpha(s[j]) = 1}
• word_start(i) = min{k | ∀j ∈ [k, i], is_alpha(s[j]) = 1}
  Then:
  last_word_length = max_{i=0..n-1} (word_end(i) - word_start(i) + 1) where word_end(i) is the last non-space position.

Constraint Analysis

• 1 <= s.length <= 10⁴:
  • Linear solutions (O(n)) are feasible, but O(n²) would be borderline (10⁸ operations)
  • Memory usage must be efficient; cannot store excessive copies of the string
• s consists of only English letters and spaces ' ':
  • No special character handling needed
  • Case sensitivity: ‘A’ and ‘a’ are both valid letters
• There will be at least one word in s:
  • No need to handle empty result case
  • But must handle single-word inputs (e.g., “Hello”)

Hidden Edge Cases

• Single word with no spaces (“Hello”)
• Multiple trailing spaces ("word ")
• Multiple leading spaces (" word")
• Single character words (“a b c d”)
• Maximum length string (10⁴ characters) with alternating letters/spaces

2. Intuition Scaffolding

Real-World Metaphor
Imagine scanning a book page from the bottom right corner upward. You first skip the blank margin (trailing spaces), then measure the last line of text until you hit the left margin or a paragraph break (space).

Gaming Analogy
In a side-scrolling platformer, your character starts at the right edge of the level and moves left. You ignore empty platforms (spaces) until you land on a solid platform (word), then measure its width until you reach a gap.

Math Analogy
Finding the length of the last non-zero segment in a binary sequence where 1=letter and 0=space. This is equivalent to finding the maximum distance between the last 1 and the previous 0 in the sequence.

Common Pitfalls

1. Using split() without considering trailing spaces:
   "hello ".split() → ["hello"] works, but "hello ".split(" ") → ["hello", ""] fails
2. Starting from beginning instead of end: Wasteful for long strings with short last word
3. Not handling single-word edge cases: May return 0 if logic depends on finding spaces
4. Counting spaces as part of word: Incorrectly including trailing spaces in length
5. Off-by-one errors: Especially when using index arithmetic for word boundaries

3. Approach Encyclopedia

Approach 1: Built-in String Functions

1. Trim trailing spaces from s
2. Split string by spaces
3. Return length of last element in split list

Complexity Proof:

• Trimming: O(n) worst-case (many trailing spaces)
• Splitting: O(n) scanning entire string
• Space: O(n) for storing split list
• Total: Time O(n), Space O(n)

Approach 2: Reverse Linear Scan (Optimal)

1. Initialize length = 0
2. Start from last character, move backward:
   a. If current char is space and length > 0: break
   b. If current char is letter: increment length
3. Return length

Complexity Proof:

• Time: Worst-case O(n) when no spaces, best-case O(1) when last char is letter
• Space: O(1) only using counters

Visualization

String: "  abc def   "
Index:   0123456789
Reverse scan:
i=9: space, length=0 → continue
i=8: space, length=0 → continue  
i=7: 'f', length=1
i=6: 'e', length=2
i=5: 'd', length=3
i=4: space, length>0 → break
Result: 3

4. Code Deep Dive

def lengthOfLastWord(s: str) -> int:
    length = 0
    # Start from end, move backward
    for i in range(len(s) - 1, -1, -1):
        if s[i] != ' ':  # Found non-space character
            length += 1
        elif length > 0:  # Found space AFTER counting a word
            break
    return length

Line-by-Line Analysis

• length = 0: Initialize counter for last word
• for i in range(len(s) - 1, -1, -1): Reverse traversal from last index to 0
• if s[i] != ' ': Current character is part of a word
• length += 1: Increment word length counter
• elif length > 0: Found space AND we’ve already started counting a word
• break: Word complete, exit early
• return length: Final word length (0 if no word, but constraints prevent this)

Edge Case Handling

• Example 2 (" fly me to the moon "):
  • Starts at last char (space), skips until ‘n’ of “moon”
  • Counts ‘n’,‘o’,‘o’,‘m’ → length=4
  • Hits space before ‘m’, breaks
• Single word ("Hello"):
  • Counts all characters from end → length=5
  • Loop completes without break

5. Complexity War Room

Hardware-Aware Analysis

• 10⁴ characters ≈ 10KB string (ASCII)
• Single pass with 2 registers (i, length) → fits in L1 cache
• Predictable reverse access pattern → CPU prefetcher friendly

Industry Comparison Table

Approach	Time	Space	Readability	Interview Viability
Built-in	O(n)	O(n)	10/10	✅ Quick solution
Reverse Scan	O(n)	O(1)	8/10	✅ Optimal solution
Forward Scan	O(n)	O(1)	6/10	❌ Less intuitive

6. Pro Mode Extras

Variants Section

• k-th Last Word: Modify to return length of k-th word from end

  def lengthOfKthLastWord(s, k):
      words = s.split()
      return len(words[-k]) if k <= len(words) else 0
  

• Words with Punctuation: Handle commas, periods as part of words
• Unicode Support: Extend to international characters beyond ASCII

Interview Cheat Sheet

• First Mention: “This can be solved in O(n) time with O(1) space using reverse iteration”
• Key Insight: “Trailing spaces are irrelevant until we’ve started counting a word”
• Testing Strategy: Test with trailing/leading spaces, single word, single character
• Optimization Path: Start with built-in solution, then optimize to reverse scan