Leetcode: Length of Last Word

This question is asked at both Google and Bloomberg. 

Given a String s consists of some words separated by spaces, return the length of the last word in the string. If the last word does not exist, return 0. 

A word is a maximal substring consisting of non-space characters only.  We want to figure out the length of the last word in the string. Here are some manipulations of the algorithm:

Example 1:

Input: s = "Hello World"

Output: 5

Example 2:

Input: s = " "

Output: 0 

We start with some approaches for manipulating several string indices, and the solution to the algorithm can be broken into 2 steps. We locate the last word and iterate through the string in reverse order. See if we consume a non-space character, and this is when you know that you consume the last character of the last word. The count the length of the last word until we reach the space. Notice, that here, you go backwards.  The time complexity of this algorithm is O(N) and the space is O(1) because only constant memory is consumed (the string) regardless of the input.

Here's the code, and then I will discuss a one-pass method about this. 

class Solution {

    public int lengthOfLastWord(String s) {

        int p = s.length() - 1;

        //move backwards and skip all the spaces. 

        while(p >= 0 && s.charAt(p) == ' ') {

            p--;

        }

        //now, we have reached

        int length = 0;

        //compute the length of the last word based on when the space is reached again.

        while(p >= 0 && s.charAt(p) != ' ') {

            p--;

            length++;

        }

        return length;

    }

}

Remember in string problems, always start from the last character first, because it is easier this way to discard spaces.

In the previous problem, there are 2 loops, where one loop is used to locate the last word, and the other loop is used to locate its length. 

We should define a condition which is the precise moment that we should start to count a word. We then count backwards until we reached the other space. We start at the length of the string, and count until we reach a ' ' character. It only does this if the length is equal to zero, which means that we haven't reached our first word yet. 

Here's the code: 

class Solution {

    public int lengthOfLastWord(String s) {

        int p = s.length();

        int length = 0;

        //iterate from the end of the word to the beginning of the word.

        while(p > 0) {

            p--;

            //add the lenght if you haven't reached the space

            if(s.charAt(p) != ' ') {

                length++;

            }

            //if the length is greater than 0, this means that we have reached the other string.

            else if (length > 0) {

                return length;

            }

        }

        return length;

    }

}