Java O(n) Easy to Understand, Optimal Solution


  • 0
    B

    Explanation
    The idea to this question is to start counting characters from the very end of the string. However, the tricky part comes from ignoring all the whitespace that comes after the last word. The question is intentionally vague about whether the string is in "valid" format or not. And... it's not.

    Time Complexity
    The time complexity is O(n) where n is the length of input s, since we scan through at most all characters in s when counting the last word's characters.

    class Solution {
        public int lengthOfLastWord(String s) {   
            int index = s.length() - 1;
            
           // Decrement index until we're past all whitespace
            while (index >= 0 && s.charAt(index) == ' ') {
                index--;
            }
           // If the entire string was whitespace, return 0 - no last word
            if (index < 0) {
                return 0;
            }
            // Count the # characters in the last word
            int count = 0;
            while (index >= 0 && s.charAt(index) != ' ') {
                count++;
                index--;
            }
            return count;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.