58. Length of Last Word

Time: O(n)

Space: O(1)

Intuition

Scan from the right: skip trailing spaces, then count characters until another space or the start of the string is reached.

Algorithm

1Set i = s.Length - 1.
2Skip trailing spaces: while i >= 0 and s[i] == " ", i--.
3Count word characters: while i >= 0 and s[i] != " ", i--, count++.
4Return count.

Example Walkthrough

Input: " fly me to the moon "

1.Skip trailing spaces at indices 28,27. i=26 ("n").
2.Count: n,o,o,m = 4. i hits space. count=4.

Output: 4

Common Pitfalls

•Do not split by spaces - "Hello World " has a trailing space that confuses Split().

58.cs

// Approach: Scan from the end of the string skipping trailing spaces,
// then count characters until the next space or the start.
// Time: O(n) Space: O(1)

public class Solution
{
    public int LengthOfLastWord(string s)
    {
        int n = s.Length;

        int len = 0;
        for (int i = n - 1; i >= 0; i--)
        {
            if (s[i] == ' ' && len == 0)
                continue;
            else if (s[i] == ' ')
                return len;

            len++;
        }

        return len;
    }
}

Was this solution helpful?