Jobs

Interviews

Discussions

Length of Last Word

Easy

Asked by:

More companies

142 views

Topics:

Strings

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.

Constraints:

1 <= s.length <= 10⁴
s consists of only English letters and spaces ' '.
There will be at least one word in s.

Try coding it in LeetCode

Length of Last Word

Easy

Asked by:

142 views

Topics:

Strings

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.

Constraints:

1 <= s.length <= 10⁴
s consists of only English letters and spaces ' '.
There will be at least one word in s.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string `s` be empty or null?
Are there any leading or trailing spaces in the input string `s` that I need to handle?
If the string `s` contains only spaces, what should the return value be?
Can I assume that the string `s` will always contain at least one word if it's not empty?
What characters other than spaces and letters can the string contain?

Brute Force Solution

Approach

The brute force method to find the length of the last word means going through the entire input and checking every possible scenario. We identify words by looking for spaces, and isolate the final word by eliminating any trailing spaces.

Here's how the algorithm would work step-by-step:

First, start at the very end of the input.
If there are spaces at the end, ignore them until a letter is found.
Once a letter of the last word is found, start counting the number of letters until a space is found.
If no space is found before the beginning of the input is reached, then the whole input is the last word and the count is the length of the input.
The number of letters counted is the length of the last word.

Code Implementation

def length_of_last_word_brute_force(input_string):
    string_length = len(input_string)
    last_word_length = 0

    # Start from the end of the string
    current_index = string_length - 1

    # Skip trailing spaces
    while current_index >= 0 and input_string[current_index] == ' ':
        current_index -= 1

    # Count the length of the last word
    while current_index >= 0 and input_string[current_index] != ' ':
        last_word_length += 1
        current_index -= 1

    return last_word_length

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the string s of length n at most once. The first loop skips trailing spaces, which in the worst case could iterate through the entire string. The second loop counts the characters of the last word, which again in the worst case could iterate through the entire string if the input consists of only one word. Therefore, the dominant operation is iterating through the string once, giving a time complexity of O(n).

Space Complexity

O(1) – The provided algorithm iterates through the input string without using any auxiliary data structures like arrays, lists, or hash maps to store intermediate results. It only uses a counter variable to keep track of the length of the last word. The space used by this counter remains constant regardless of the input string length, N.

Optimal Solution

Approach

The most efficient way to find the length of the last word is to start from the end of the sentence and work backwards. We can ignore any trailing spaces and stop counting characters once we hit the beginning of the last word or the start of the sentence.

Here's how the algorithm would work step-by-step:

Begin at the very end of the sentence.
Skip over any spaces you find at the end until you reach a letter.
Once you find a letter, start counting how many letters you see.
Keep counting letters until you either reach another space or the beginning of the sentence.
The number of letters you counted is the length of the last word.

Code Implementation

def length_of_last_word(sentence):
    sentence_length = len(sentence)
    last_word_length = 0

    # Start from the end of the sentence.
    for i in range(sentence_length - 1, -1, -1):
        if sentence[i] != ' ':
            # Found a letter, start counting.
            last_word_length += 1
        else:
            # If we have counted some letters
            if last_word_length > 0:

                # Then we've found the end of the word
                return last_word_length

    # Handle the case where there are no spaces
    return last_word_length

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the string 's' at most once, starting from the end. The first loop skips trailing spaces, and the second loop counts characters in the last word until a space or the beginning of the string is encountered. The number of iterations in both loops is bounded by the length 'n' of the string 's'. Therefore, the time complexity is directly proportional to 'n', resulting in O(n).

Space Complexity

O(1) – The algorithm iterates through the string using index variables, but it doesn't create any additional data structures whose size depends on the input string length N. It only uses a counter for the length of the last word. Therefore, the auxiliary space used is constant, independent of the input size N.

Edge Cases

Case	How to Handle
Null or empty input string	Return 0 immediately as there are no words.
String with only spaces	Return 0 because there are no non-space words.
String with leading and trailing spaces	Trim the string before processing to remove extra spaces.
String with multiple spaces between words	Trimmed string will now have one space, or we can iterate backwards skipping spaces.
String with a single word and no spaces	The length of the word is the length of the entire string.
Very long string to check performance/efficiency	Iterating backwards provides O(n) linear time complexity which scales appropriately.
String ending with multiple spaces after last word	Trim the string to remove them, or check for space before counting.
String with unicode characters	Ensure the language properly handles unicode string length and character access.

Null or empty input string

How to Handle:

Return 0 immediately as there are no words.

String with only spaces

How to Handle:

Return 0 because there are no non-space words.

String with leading and trailing spaces

How to Handle:

Trim the string before processing to remove extra spaces.

String with multiple spaces between words

How to Handle:

Trimmed string will now have one space, or we can iterate backwards skipping spaces.

String with a single word and no spaces

How to Handle:

The length of the word is the length of the entire string.

Very long string to check performance/efficiency

How to Handle:

Iterating backwards provides O(n) linear time complexity which scales appropriately.

String ending with multiple spaces after last word

How to Handle:

Trim the string to remove them, or check for space before counting.

String with unicode characters

How to Handle:

Ensure the language properly handles unicode string length and character access.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string `s` be empty or null?
Are there any leading or trailing spaces in the input string `s` that I need to handle?
If the string `s` contains only spaces, what should the return value be?
Can I assume that the string `s` will always contain at least one word if it's not empty?
What characters other than spaces and letters can the string contain?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, start at the very end of the input.
If there are spaces at the end, ignore them until a letter is found.
Once a letter of the last word is found, start counting the number of letters until a space is found.
If no space is found before the beginning of the input is reached, then the whole input is the last word and the count is the length of the input.
The number of letters counted is the length of the last word.

Code Implementation

def length_of_last_word_brute_force(input_string):
    string_length = len(input_string)
    last_word_length = 0

    # Start from the end of the string
    current_index = string_length - 1

    # Skip trailing spaces
    while current_index >= 0 and input_string[current_index] == ' ':
        current_index -= 1

    # Count the length of the last word
    while current_index >= 0 and input_string[current_index] != ' ':
        last_word_length += 1
        current_index -= 1

    return last_word_length

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Begin at the very end of the sentence.
Skip over any spaces you find at the end until you reach a letter.
Once you find a letter, start counting how many letters you see.
Keep counting letters until you either reach another space or the beginning of the sentence.
The number of letters you counted is the length of the last word.

Code Implementation

def length_of_last_word(sentence):
    sentence_length = len(sentence)
    last_word_length = 0

    # Start from the end of the sentence.
    for i in range(sentence_length - 1, -1, -1):
        if sentence[i] != ' ':
            # Found a letter, start counting.
            last_word_length += 1
        else:
            # If we have counted some letters
            if last_word_length > 0:

                # Then we've found the end of the word
                return last_word_length

    # Handle the case where there are no spaces
    return last_word_length

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return 0 immediately as there are no words.
String with only spaces	Return 0 because there are no non-space words.
String with leading and trailing spaces	Trim the string before processing to remove extra spaces.
String with multiple spaces between words	Trimmed string will now have one space, or we can iterate backwards skipping spaces.
String with a single word and no spaces	The length of the word is the length of the entire string.
Very long string to check performance/efficiency	Iterating backwards provides O(n) linear time complexity which scales appropriately.
String ending with multiple spaces after last word	Trim the string to remove them, or check for space before counting.
String with unicode characters	Ensure the language properly handles unicode string length and character access.

Null or empty input string

How to Handle:

Return 0 immediately as there are no words.

String with only spaces

How to Handle:

Return 0 because there are no non-space words.

String with leading and trailing spaces

How to Handle:

Trim the string before processing to remove extra spaces.

String with multiple spaces between words

How to Handle:

Trimmed string will now have one space, or we can iterate backwards skipping spaces.

String with a single word and no spaces

How to Handle:

The length of the word is the length of the entire string.

Very long string to check performance/efficiency

How to Handle:

Iterating backwards provides O(n) linear time complexity which scales appropriately.

String ending with multiple spaces after last word

How to Handle:

Trim the string to remove them, or check for space before counting.

String with unicode characters

How to Handle:

Ensure the language properly handles unicode string length and character access.