Solving LeetCode - Length of Last Word in Java

The "Length of Last Word" problem is a fundamental string processing challenge that tests your understanding of string manipulation and edge case handling. Let's explore multiple approaches to solve this problem efficiently.

Problem Statement

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.

Solution Strategies

Approach 1: Right-to-Left Traversal (Optimal)

The most efficient approach is to traverse the string from right to left, skipping trailing spaces and counting characters of the last word.

public class Solution {
    public int lengthOfLastWord(String s) {
        int length = 0;
        int i = s.length() - 1;

        // Skip trailing spaces
        while (i >= 0 && s.charAt(i) == ' ') {
            i--;
        }

        // Count characters of the last word
        while (i >= 0 && s.charAt(i) != ' ') {
            length++;
            i--;
        }

        return length;
    }
}

Time Complexity: O(n) in worst case, O(1) in best case Space Complexity: O(1)

Approach 2: Using Built-in String Methods

A more concise solution using Java's built-in string methods:

public class Solution {
    public int lengthOfLastWord(String s) {
        s = s.trim(); // Remove leading and trailing spaces
        int lastSpaceIndex = s.lastIndexOf(' ');
        return s.length() - lastSpaceIndex - 1;
    }
}

Time Complexity: O(n) Space Complexity: O(1) if trim() modifies in place, O(n) otherwise

Approach 3: Split and Take Last

Using the split method (less efficient but readable):

public class Solution {
    public int lengthOfLastWord(String s) {
        String[] words = s.trim().split("\\s+");
        return words[words.length - 1].length();
    }
}

Time Complexity: O(n) Space Complexity: O(n) for the array of words

Key Insights

1. Edge Case Handling: Always consider strings with trailing spaces
2. Efficiency: Right-to-left traversal is most efficient as it can terminate early
3. String Methods: Built-in methods can simplify code but may have hidden complexity
4. Memory Usage: Be aware of space complexity when using split or trim operations

Conclusion

The right-to-left traversal approach is optimal for this problem, offering the best time complexity and minimal space usage. It handles all edge cases elegantly and demonstrates good algorithmic thinking.

This problem is an excellent introduction to string processing patterns and showcases the importance of considering edge cases in algorithm design.