Length of Last Word

In this article, we’ll explore different approaches to solving this problem, from brute force solution to a more optimized solution. So buckle up, grab a cup of coffee (or tea, we don’t discriminate), and let’s dive in!

Problem Statement:

Given a string s consisting of words and spaces, return the length of the last word in the string.

After reading the problem statement, it looks easy, doesn’t it? You might be tempted to rely on the trusty built-in methods of JavaScript to solve it. But hold on, my friend — in a tech interview, you can never be too sure what twists and turns await you.

That’s why interviewers often pose these simple problems as a test of your critical thinking and problem-solving skills. Sure, you could slap together a solution using built-in methods, but where’s the fun in that? You’ll be challenged to dig deeper and optimize your approach, demonstrating your programming skills and your ability to tackle complex problems head-on.

So, let’s get cracking on this problem. We will start with the built-in methods and then explore a more optimized solution.

---

Approach 1: Trim, Split and Length

1. The trim()method removes whitespace from both ends of a string and returns a new string, without modifying the original string. Time complexity is O(N)

2. The split() method is used to split a string into an array of substrings based on a specified separator. Time complexity is O(N)

3. So we will first create a new array arr of substrings by trimming and splitting the input string.

4. Then we will return the length of the last element in the arr.

// ES6 Arrow Function
const lengthOfLastWord = s => {
    let arr = s.trim().split(' ');
    return arr[arr.length - 1].length;
}

Time Complexity: O(N)

Space Complexity: O(N)

---

Note: The time and space complexity of the above solution are both linear. However, it is possible to make some modifications to the solution to achieve constant space complexity.

Approach 1.1

1. Create a new string str after trimming the input string s.

2. Return the difference of str.length and str.lastIndexOf(' ') - 1.

3. str.lastIndexOf(' ') finds the last index of the space character in str.

// ES6 Arrow Function
const lengthOfLastWord = s => {
    let str = s.trim();

    return str.length - str.lastIndexOf(' ') - 1;
}

Time Complexity: O(N)

Space Complexity: O(1)

---

Now coming to the solution that doesn’t use built-in functions like lastIndexOf() or trim()

Approach 2:

1. Initialize a variable to store the length of the last word and a pointer to the end of the input string.

2. Loop through the input string from right to left, skipping all the white space characters at the end of the string by decrementing the pointer until the first non-space character is found.

3. Loop through the input string from the pointer to the left, counting the number of characters until the first space character is found. Increase the value of the length variable by 1 for each non-space character found.

4. Return the value of the length variable as the length of the last word in the input string.

// ES6 Arrow Function
const lengthOfLastWord = s => {
    let len = 0, tail = s.length - 1;

    while(tail >= 0 && s[tail] == ' ') tail--;
    while(tail >= 0 && s[tail] != ' ') {
        len++;
        tail--;
    }

    return len;
}

Time Complexity: O(N)

Space Complexity: O(1)

---

Note: This can be simplified using just one loop.

Approach 2.1

1. Declare a variable to store the length.

2. Iterate the input string from right to left and for each non-space character increase the value of the length variable by 1.

3. If the character encountered is a white space then check if the value of the length variable is more than 0 or not.

4. If the length variable is greater than 0, then the length of the last word has been found. Return the value of the length variable.

// ES6 Arrow Function
const lengthOfLastWord = s => {
    let len = 0;

    for(let i = s.length - 1; i >= 0; i--) {
        if(s.charAt(i) !== ' ') len++;
        else {
            if(len > 0) return len;
        }
    }

    return len;
}

Time Complexity: O(N)

Space Complexity: O(1)

---

And there you have it guys! We’ve explored different approaches, optimized our solutions, and hopefully had some fun along the way. I hope this article has provided you with valuable insights and helped you better understand the different approaches to solving this problem. Happy coding!

Problem: Leetcode 58