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 sub-string consisting of non-space characters only.

Clarifying Questions

1. Q: What should be returned if the string is empty or contains only spaces? A: For an empty string or a string with only spaces, the expected output should be 0 since there are no words.

2. Q: Are there any constraints on the input string length? A: Usually, strings in such problems can be reasonably assumed to be within typical constraints, like up to (10^4) characters.

Strategy

1. Trim Trailing Spaces: We need to discard any trailing spaces at the end of the string to correctly identify the last word.
2. Find the Last Word:
   • Start from the end of the trimmed string and move backwards to find the beginning of the last word.
   • Count the length as we find the characters of the last word.

Code

#include <iostream>
#include <string>
#include <algorithm> // for std::find_if

int lengthOfLastWord(const std::string &s) {
    int length = 0;
    int i = s.size() - 1;

    // Skip trailing spaces
    while (i >= 0 && s[i] == ' ') --i;

    // Count length of last word
    while (i >= 0 && s[i] != ' ') {
        --i;
        ++length;
    }
    
    return length;
}

int main() {
    std::string test1 = "Hello World";
    std::string test2 = "   fly me   to   the moon  ";
    std::string test3 = "luffy is still joyboy";
    std::string test4 = "       ";

    std::cout << lengthOfLastWord(test1) << std::endl; // Output: 5
    std::cout << lengthOfLastWord(test2) << std::endl; // Output: 4
    std::cout << lengthOfLastWord(test3) << std::endl; // Output: 6
    std::cout << lengthOfLastWord(test4) << std::endl; // Output: 0

    return 0;
}

Time Complexity

• The time complexity of this solution is (O(n)), where (n) is the length of the string s. This is because, in the worst case, we may need to traverse the entire string to skip leading spaces and count the length of the last word.
• The space complexity is (O(1)) since we only use a few extra variables for counting and indexing.

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?