Code Implementation

class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        i = len(s) - 1
        # Skip trailing spaces
        while i >= 0 and s[i] == ' ':
            i -= 1
        length = 0
        # Count length of last word
        while i >= 0 and s[i] != ' ':
            length += 1
            i -= 1
        return length
      

class Solution {
public:
    int lengthOfLastWord(string s) {
        int i = s.size() - 1;
        // Skip trailing spaces
        while (i >= 0 && s[i] == ' ') i--;
        int length = 0;
        // Count length of last word
        while (i >= 0 && s[i] != ' ') {
            length++;
            i--;
        }
        return length;
    }
};
      

class Solution {
    public int lengthOfLastWord(String s) {
        int i = s.length() - 1;
        // Skip trailing spaces
        while (i >= 0 && s.charAt(i) == ' ') i--;
        int length = 0;
        // Count length of last word
        while (i >= 0 && s.charAt(i) != ' ') {
            length++;
            i--;
        }
        return length;
    }
}
      

var lengthOfLastWord = function(s) {
    let i = s.length - 1;
    // Skip trailing spaces
    while (i >= 0 && s[i] === ' ') i--;
    let length = 0;
    // Count length of last word
    while (i >= 0 && s[i] !== ' ') {
        length++;
        i--;
    }
    return length;
};
      

Problem Description

Given a string s consisting of words and spaces, return the length of the last word in the string. A word is defined as a maximal substring consisting of non-space characters only.

• The input s may contain leading or trailing spaces.
• You should only consider the last word (ignoring any spaces after it).
• There will always be at least one word in s.

Constraints:

• 1 ≤ s.length ≤ 10⁴
• s consists of only English letters and spaces ' '.

Thought Process

At first glance, the problem appears simple—just find the last word and return its length. However, there are edge cases to consider, such as trailing spaces or multiple spaces between words. A brute-force approach might be to split the string by spaces and pick the last non-empty substring, but this may use extra memory and be less efficient.

To optimize, we can process the string from the end, skipping any trailing spaces, and then count the characters of the last word until we hit a space or the start of the string. This avoids extra space and is efficient.

This approach is akin to reading a sentence backwards, ignoring any empty space at the end, and then counting the letters of the first word you encounter.

Solution Approach

• Step 1: Start from the end of the string (i.e., the last character).
• Step 2: While the current character is a space, move backwards to skip all trailing spaces.
• Step 3: Once a non-space character is found, this marks the end of the last word. Initialize a counter.
• Step 4: Continue moving backwards, counting each character, until you hit a space or reach the beginning of the string.
• Step 5: Return the counter, which now holds the length of the last word.

This approach is chosen because:

• It operates in O(n) time, where n is the length of the string.
• It uses O(1) extra space; no additional data structures are needed.
• It handles all edge cases, including multiple spaces and strings with only one word.

Example Walkthrough

Input: s = "Hello World "

1. Start at the end: index points to the last character (which is a space).
2. Skip spaces: Move left until you reach the character 'd' in "World".
3. Begin counting: For each character ('d', 'l', 'r', 'o', 'W'), increment the counter.
4. Stop when a space or the beginning of the string is reached (before 'W').
5. The counter now holds 5, which is the length of "World".

This process ensures that even if there are extra spaces at the end, they are ignored, and only the last word is considered.

Time and Space Complexity

• Brute-force approach:
  • Splitting the string by spaces and filtering out empty words takes O(n) time and O(n) space (for the split array).
• Optimized approach (used here):
  • Time Complexity: O(n), as we may need to scan the entire string once.
  • Space Complexity: O(1), since only a few variables are used for indexing and counting.

The optimized approach is preferred for large inputs due to its constant space usage and linear time.

Summary

The "Length of Last Word" problem is elegantly solved by scanning the string from the end, skipping any trailing spaces, and counting the characters of the final word. This approach is efficient, concise, and handles all edge cases without any extra memory allocation. The key insight is to avoid unnecessary splitting or extra data structures and work directly with the characters of the string.