Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Length of Last Word

Try it yourself
EasyProblemExternal link

Description

You get a string s made of words and spaces. Return the length of the last word in the string.

A word is a maximal run of characters that are not spaces.

Examples

Example 1

Input: s = "Hello World"

Output: 5

Explanation: The last word is World, which has 5 letters.

Example 2

Input: s = " fly me to the moon "

Output: 4

Explanation: Spaces at the end don't count: the last word is moon, 4 letters.

Example 3

Input: s = "luffy is still joyboy"

Output: 6

Explanation: The last word is joyboy, 6 letters.

Constraints

  • 1 ≤ s.length ≤ 10^4
  • s consists of only English letters and spaces ' '.
  • There will be at least one word in s.

Editorial

Brute Force

Intuition

Split the string into words, which handles any number of spaces anywhere, and measure the last one.

Step-by-Step Explanation

Let's split s = " fly me to the moon ":

  1. Split the string into its words, skipping every run of spaces.
  2. Word 1 is "fly".
  3. Word 2 is "me".
  4. Word 3 is "to".
  5. Word 4 is "the".
  6. Word 5 is "moon".
  7. The last word is "moon", 4 letters. Every word was stored to get there.

Split Into Words — Each step finds one word, in indigo; the last one turns green.

Algorithm

  1. Split s on runs of spaces.
  2. Return the length of the last word.

Code

class Solution {
public:
    int lengthOfLastWord(string s) {
        vector<string> words;
        string word;
        for (char c : s) {                          // split into every word first
            if (c != ' ') word += c;
            else if (!word.empty()) { words.push_back(word); word.clear(); }
        }
        if (!word.empty()) words.push_back(word);
        return words.back().size();
    }
};

class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        words = s.split()                       # every word, as a list
        return len(words[-1])

class Solution {
    public int lengthOfLastWord(String s) {
        String[] words = s.trim().split("\\s+");     // every word, as an array
        return words[words.length - 1].length();
    }
}

var lengthOfLastWord = function(s) {
    const words = s.trim().split(/\s+/);        // every word, as an array
    return words[words.length - 1].length;
};

Complexity Analysis

Time Complexity: O(n)

One pass to split.

Space Complexity: O(n)

Every word is stored, though only the last one is needed.

Why This Approach Is Not Efficient

It's already O(n) time, and it passes every test. The waste is space: it stores every word to read one. The last word is at the end of the string, so read the string from the end instead.

Optimal Approach - Walk Back From the End

Intuition

Start at the last character. Skip the spaces at the end, then count characters until a space or the start of the string. Nothing else in the string needs to be looked at.

Step-by-Step Explanation

Let's walk s = " fly me to the moon " from the end:

  1. Start at the last character and walk left, first past the spaces, then through the last word.
  2. Index 26 is a space at the end. Skip it.
  3. Index 25 is a space at the end. Skip it.
  4. 'n' belongs to the last word. The length is 1.
  5. 'o' belongs to the last word. The length is 2.
  6. 'o' belongs to the last word. The length is 3.
  7. 'm' belongs to the last word. The length is 4.
  8. Index 20 is a space, so the word has ended with 4 letters, and nothing was stored.

Walk Back From the End — Amber: a space at the end, skipped. Green: the last word, counted.

Algorithm

  1. Set i to the last index; move it left while s[i] is a space.
  2. Count characters, moving left, while i >= 0 and s[i] isn't a space.
  3. Return the count.

Code

class Solution {
public:
    int lengthOfLastWord(string s) {
        int i = (int)s.size() - 1;
        while (i >= 0 && s[i] == ' ') i--;          // skip the spaces at the end
        int length = 0;
        while (i >= 0 && s[i] != ' ') {             // count back to the start of the last word
            length++;
            i--;
        }
        return length;
    }
};

class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        i = len(s) - 1
        while i >= 0 and s[i] == " ":           # skip the spaces at the end
            i -= 1
        length = 0
        while i >= 0 and s[i] != " ":           # count back to the start of the last word
            length += 1
            i -= 1
        return length

class Solution {
    public int lengthOfLastWord(String s) {
        int i = s.length() - 1;
        while (i >= 0 && s.charAt(i) == ' ') i--;   // skip the spaces at the end
        int length = 0;
        while (i >= 0 && s.charAt(i) != ' ') {      // count back to the start of the last word
            length++;
            i--;
        }
        return length;
    }
}

var lengthOfLastWord = function(s) {
    let i = s.length - 1;
    while (i >= 0 && s[i] === ' ') i--;         // skip the spaces at the end
    let length = 0;
    while (i >= 0 && s[i] !== ' ') {            // count back to the start of the last word
        length++;
        i--;
    }
    return length;
};

Complexity Analysis

Time Complexity: O(n)

At worst the walk crosses the whole string.

Space Complexity: O(1)

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Splitting on a single space. return len(s.split(" ")[-1])

On s = " fly me to the moon " it returns 0; the answer is 4. s.split(" ") keeps the empty strings between spaces, so with spaces at the end the last piece is empty and the answer comes out 0. split() with no argument, or walking from the end, ignores them.

Counting from the very end. while i >= 0 and s[i] != " ":

On s = " fly me to the moon " it returns 0; the answer is 4. Counting back from the last character stops at once when the string ends with a space. Skip the spaces at the end first.

Measuring the first word. return len(s.split()[0])

On s = " fly me to the moon " it returns 3; the answer is 4. Reading from the left finds the first word. The question asks for the last one.

Where This Pattern Is Taught

Walking a string with an index, and splitting it carefully, are taught in Introduction to Strings.