Length of Last Word – 58. LeetCode

The “Length of Last Word” problem asks us to find the length of the last word in a given string. A word is defined as a maximal substring consisting only of non-space characters. The problem may involve handling edge cases like multiple trailing spaces or no words at all. It is a simple string manipulation problem often used to test a candidate’s ability to handle basic string operations efficiently.

Brute Force Approach

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

• Remove leading and trailing spaces to avoid complication with extra spaces.
• Split the string by spaces to create an array of words.
• Access the last element of the array and return its length.

• Time Complexity:  O(n)  for traversing the string during trim and split.

• Space Complexity:  O(n)  for storing the array of words.

Optimized Approach

Algorithm and Data Structure

1. Algorithm:

• Iterate through the string in reverse to find the last word without splitting or creating intermediate arrays.

• Skip trailing spaces, then count the characters in the last word.

2. Data Structure:

• No additional data structure is required; the solution works directly with the string.

• The problem is well-suited for a reverse traversal because:

• The last word is found at the end of the string.

• Trailing spaces can be ignored while traversing backward.

• By avoiding string splitting or extra arrays, we minimize both time and space usage.

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

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

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

    return length;
}

Line By Line Explanation

Step 1: Initialize Variables

int length = 0;
int i = s.length() - 1;

Step 2: Skip Trailing Space

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

• Skips spaces at the end of the string.
• Ensures the pointer starts at the last character of the last word.

Step 3: Count Characters in the Last Word

while (i >= 0 && s.charAt(i) != ' ') {
    length++;
    i--;
}

• Counts non-space characters until the start of the string or a space is encountered.

Step 4: Return

return length;

• Returns the length of the last word.

Why This Code Works

• The optimized approach minimizes both time and space usage by directly iterating over the string.

• The reverse traversal aligns with efficient algorithmic patterns, making it ideal for scenarios with stringent memory or performance constraints.

• Handling edge cases and understanding trade-offs are critical in designing a robust solution.