58. Length of Last Word

EasyString
Leetcode Link

Problem Description

The problem requires us to find the length of the last word in a given string s. The string consists of English letters and spaces (' '). Words can be considered as sequences of characters separated by one or more spaces. Importantly, we're only interested in the length of the last word, not the word itself. This means that we need to traverse the string to separate the last word from possible trailing spaces and then measure its length.

Intuition

To solve this problem, we realize that the last word in the string could possibly be followed by spaces. If we start scanning from the end of the string, the first non-space character we encounter marks the end of the last word. We record this position as i. We then continue scanning backwards till we find the first space character or reach the beginning of the string; this indicates the position right before the start of the last word, which we denote as j. So the length of the last word is simply the difference between i and j.

Now, let's go step-by-step to reach this solution:

  1. Start scanning from the end of the string to bypass any trailing spaces if they exist.
  2. Once a non-space character is found, this is the last character of the last word; mark this position i.
  3. Continue scanning backwards until we find a space character or the beginning of the string; this marks the position before the start of the last word, j.
  4. Calculate the length of the last word as i - j.

This approach works because we need to find only the last word, which allows us to use a reverse scan, thus eliminating the need to process the entire string or the other words. As a result, we obtain a solution that is efficient in both time and space.

Time complexity is O(n) because, in the worst case, we might traverse the entire string if the last word is at the beginning or if there is only one word. Space complexity is O(1), as no additional space is required that is dependent on the size of the input string.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following is a min heap?

Solution Approach

The implementation of the solution is direct and utilize a simple algorithm without needing any additional data structures. We directly process the string itself using two pointers.

Let's describe the steps that correspond to the provided Python code:

  1. Initialize i to point to the last character of the string s. This is done by setting i = len(s) - 1.

  2. Use a while loop to decrement i until we find a non-space character. This loop skips any trailing spaces that might be at the end of the string s. The condition i >= 0 ensures we don't go out of bounds if the entire string is composed of spaces.

  3. Once the loop finds a non-space character, i points to the last character of the last word. We then use j = i to mark the end of the last word.

  4. Another while loop is used to continue moving j backwards (j -= 1) until it finds a space character or until we reach the start of the string. This gives us the position just before the start of the last word.

  5. Finally, we calculate the length of the last word using i - j. Since j is the position before the first character of the last word, i - j correctly gives the length of the last word.

No additional data structures are necessary because the solution modifies the existing input only by keeping count of the current index with the pointers i and j, and does not modify the string itself.

The pattern used in this solution is known as the two pointers technique, which is often used in array and string manipulation problems to track or compare elements from the start/end or both.

Considering the complexity:

  • The time complexity is O(n) because we potentially have to traverse the entire string if the last word is at the beginning or if there's only one word without leading or trailing spaces.
  • Space complexity is O(1), meaning that the space used by the algorithm does not grow with the input size. We only use a finite amount of additional memory for the pointers and condition checking.

Here is the approach with the code blocks:

1class Solution:
2    def lengthOfLastWord(self, s: str) -> int:
3        # Initialize i to the last index of the string
4        i = len(s) - 1
5      
6        # Skip any trailing spaces
7        while i >= 0 and s[i] == ' ':
8            i -= 1
9      
10        # i now points to the last character of the last word
11        j = i
12      
13        # Find the space before the start of the last word
14        while j >= 0 and s[j] != ' ':
15            j -= 1
16      
17        # The length of the last word is the difference between i and j
18        return i - j

Using these pointers, the solution efficiently calculates the length of the last word in the input string.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

Example Walkthrough

Let's consider a string s with the value "Hello LeetCode ".

  1. First, we initialize i to the index of the last character in s. Thus, i = len("Hello LeetCode ") - 1, which means i = 14.

  2. Starting from the end of the string, we run a while loop that decreases i until we find a non-space character. Since the last character is a space, we decrement i. It continues until i = 12 which is right before the space (pointing to 'e').

  3. At this stage s[i] is not a space, so we move out of the first while loop. We set j = i to mark the end of the last word, which in this case is j = 12.

  4. The second while loop starts decreasing j until we find a space character or reach the beginning of the string. Traversing backward, the space at index 5 is found, so j becomes 5. We've now identified the position right before the start of the last word.

  5. Finally, we calculate the length of the last word as the difference between i and j, plus one to account for the indexing (since j is right before the first character of the last word). Therefore, the length is 12 - 5, resulting in 7.

Following this approach, we can say the last word, "LeetCode", has a length of 7 characters without using additional data structures or traversing unnecessary parts of the string.

Solution Implementation

1class Solution:
2    def lengthOfLastWord(self, s: str) -> int:
3        # Start from the end of the string and find the index of the first non-space character
4        end_index = len(s) - 1
5        while end_index >= 0 and s[end_index] == ' ':
6            end_index -= 1
7      
8        # Find the beginning of the word (the index of the space before the word or -1 if the word is at the start)
9        start_index = end_index
10        while start_index >= 0 and s[start_index] != ' ':
11            start_index -= 1
12      
13        # Return the length of the last word, which is the difference between the end and start indices
14        # Add 1 because end_index is the last character of the last word and
15        # start_index is the space before the last word (or -1 if the word is at the start)
16        return end_index - start_index
17
18# Example usage:
19# sol = Solution()
20# length = sol.lengthOfLastWord("Hello World  ")
21# print(length)  # Should print 5, which is the length of "World"
22
1class Solution {
2    // Method to find the length of the last word in a string.
3    public int lengthOfLastWord(String s) {
4        // Initialize index 'endIndex' to point to the end of the string.
5        int endIndex = s.length() - 1;
6      
7        // Skip all the trailing spaces if any.
8        while (endIndex >= 0 && s.charAt(endIndex) == ' ') {
9            endIndex--;
10        }
11      
12        // Initialize index 'startIndex' to keep track of the start of the last word.
13        int startIndex = endIndex;
14      
15        // Move 'startIndex' backwards until we find a space or reach the beginning of the string.
16        while (startIndex >= 0 && s.charAt(startIndex) != ' ') {
17            startIndex--;
18        }
19      
20        // The length of the last word is the difference between 'endIndex' and 'startIndex'.
21        // We add 1 because 'startIndex' is either pointing to a space or one position off the string.
22        return endIndex - startIndex;
23    }
24}
25
1#include <string>  // Include the string library to use the std::string class
2
3class Solution {
4public:
5    // Function to calculate the length of the last word in a string
6    int lengthOfLastWord(std::string s) {
7        // Initialize `index` to the last character of the string
8        int index = s.size() - 1;
9      
10        // Skip the trailing spaces if there are any
11        while (index >= 0 && s[index] == ' ') {
12            --index; // Move backwards in the string
13        }
14      
15        // Memorize the position of the end of the last word (after skipping trailing spaces)
16        int endOfWordIndex = index;
17
18        // Find the beginning of the last word
19        while (index >= 0 && s[index] != ' ') {
20            --index; // Continue moving backwards until we find a space or reach the beginning of the string
21        }
22      
23        // Calculate the length of the last word
24        // The length is the difference between the position of the end of the word and
25        // the position of the beginning of the word (or -1 if the word starts at the beginning of the string)
26        int lengthOfLastWord = endOfWordIndex - index;
27
28        // Return the length of the last word
29        return lengthOfLastWord;
30    }
31};
32
1function lengthOfLastWord(s: string): number {
2    // Initialize the index to the last character of the string
3    let endIndex = s.length - 1;
4  
5    // Move the index backwards to skip any trailing spaces
6    while (endIndex >= 0 && s[endIndex] === ' ') {
7        endIndex--;
8    }
9  
10    // If the entire string was spaces, return 0
11    if (endIndex < 0) {
12        return 0;
13    }
14
15    // Initialize the start index to the position of the endIndex
16    let startIndex = endIndex;
17  
18    // Move the startIndex backwards until a space is encountered or the start of the string
19    while (startIndex >= 0 && s[startIndex] !== ' ') {
20        startIndex--;
21    }
22  
23    // The length of the last word is the difference between the endIndex and startIndex
24    return endIndex - startIndex;
25}
26
27// The function can be tested with the following examples:
28console.log(lengthOfLastWord("Hello World")); // Output: 5
29console.log(lengthOfLastWord(" ")); // Output: 0
30console.log(lengthOfLastWord("a ")); // Output: 1
31
Not Sure What to Study? Take the 2-min Quiz：

Which of the following problems can be solved with backtracking (select multiple)

Time and Space Complexity

Time Complexity

The time complexity of the code is O(n), where n is the length of the string s. This is because the algorithm consists of a reverse traversal for both leading spaces and the length of the last word. Each traversal individually takes at worst case O(n) time (if the string is either only spaces or has no spaces). However, these two loops are traversed sequentially, not nested, so the overall time complexity remains O(n).

Space Complexity

The space complexity of the code is O(1). This is because no additional space that scales with input size is being used. The variables i and j are used for indexing and do not depend on the size of the input string, hence they use a constant amount of space.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of these pictures shows the visit order of a depth-first search?

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫