algoadvance

Leetcode 58. Length of Last Word

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.

Clarifying Questions:

1. Input constraints: Can the input string contain leading or trailing spaces?
   • Yes, the input string can contain leading and trailing spaces.
2. Empty string: What should be returned for an empty string or string with only spaces?
   • If the string is empty or consists only of spaces, the output should be 0.

Strategy:

1. Trim spaces: Use Java’s trim() method to remove leading and trailing spaces.
2. Split the words: Split the trimmed string by spaces to get all the words.
3. Find the last word: The last element of the split array will be the last word.
4. Return the length: Return the length of this last word.

Code:

Let’s go ahead and implement the solution in Java.

public class Solution {
    public int lengthOfLastWord(String s) {
        // Trim the string to remove leading and trailing spaces
        s = s.trim();
        
        // Handle edge case where the string is empty
        if (s.isEmpty()) {
            return 0;
        }
        
        // Split the string by spaces
        String[] words = s.split(" ");
        
        // Get the last word
        String lastWord = words[words.length - 1];
        
        // Return the length of the last word
        return lastWord.length();
    }
}

Time Complexity:

• Trimming the spaces: This operation is O(n) where n is the length of the string.
• Splitting the string: This operation is O(n) because, in the worst case, it has to traverse all characters once.
• Accessing the last word and computing its length: This operation is O(1) as it involves accessing the last element of the array and calculating its length.

Overall, the time complexity for the solution is O(n).

Space Complexity:

• The primary space usage comes from the storage needed for the words array after splitting the string. In the worst case, this would be O(n).

This solution efficiently computes the length of the last word in the given string with linear time complexity regarding the length of the input string.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?