Problem Statement
In this problem a multiword string is given and we have to return the length of the last word present in that string. If there are no words we have to return 0.
Example
s = "Hello World"
5
Explanation: Length of the last word “World” is 5.
s = " "
0
Explanation: As there are no word, answer is 0.
Approach
To solve this problem first we have to trim all the whitespaces present in the string at both the ends. Then we can find the length of the last word by iterating the string from first character to last character. For trimming we can use two variables ‘start’ and ‘end’ which will store the index of first character and last character in the given string respectively.
For finding the index of the first character, initialize variable ‘start’=0.
Now simply use a while loop and increment the value in the variable till we do not get first character.
Similarly for last character initialize variable with n-1 where n is the size of the given string and decrement its value in while loop until we do not get first character(from end).
if start>end then it means there are no any character in the input string, hence return 0.
else we have our actual string.
Now to find the length of the last word we can now take an iterating variable pos to iterate the actual string from the end until we do not encounter any whitespace OR we reach to the first character of the string.
Now we return the difference between the last character index (stored in variable end) and current index which is stored in variable pos.
Implementation
C++ Program for Length of Last Word
#include <bits/stdc++.h> using namespace std; int lengthOfLastWord(string s) { int n=s.size(); if(n==0) return 0; int start,end; start=0; while(start< n && s[start]==' ') start++; //left trim end=n-1; while(end >=0 && s[end]==' ') end--; //right trim if(start>end) return 0; int pos=end; while(pos>=start) { if(s[pos]==' ') return end-pos; else pos--; } return end-pos; } int main() { string s="Hello World"; cout<<lengthOfLastWord(s)<<endl; return 0; }
5
Java Program for Length of Last Word
import java.util.*; import java.lang.*; class LastWord { public static int lengthOfLastWord(String s) { int n=s.length(); if(n==0) return 0; int start,end; start=0; while(start< n && s.charAt(start)==' ') start++; //left trim end=n-1; while(end >=0 && s.charAt(end)==' ') end--; //right trim if(start>end) return 0; int pos=end; while(pos>=start) { if(s.charAt(pos)==' ') return end-pos; else pos--; } return end-pos; } public static void main(String args[]) { String s="Hello World"; System.out.println(lengthOfLastWord(s)); } }
5
Complexity Analysis for Length of Last Word
Time Complexity
O(n) : Where n is the length of the input string. Because we are iterating through the string in a single loop and in worst case it can go to the first character.
Space Complexity
O(1) : Constant memory is consumed, regardless the input.