Find the largest word in a String

Problem: Given a String, find the largest word in the string.

Examples:

Example 1:
Input: string s=”Google Doc”
Output: “Google”

Explanation: Google is the largest word in the given string.

Example 2:
Input: string s=”Microsoft Teams”
Output: “Microsoft”
Explanation: Microsoft is the largest word in the given string

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Intuition :

-> We will compute the length using a pointer and compare it with the maximum length we encountered so far.

-> If we encounter a greater length we will update the maximum length.

->Finally, we will output this maximum word.

Approach:

-> We will be using 2 pointers i and j, i will be initialized at 0 and j will also be initialized at 0.

-> We will have max_length to store the maximum length of the string, max_start to store the starting index of the maximum length word, max_word to store the largest word

-> If we encounter ‘ ‘ or ‘\0’ in the Word, the current length of the word will be (j-i) and compare it with max_length.

->If it’s greater, we will update the max_length and max_start.

->Finally we will update max_word by using max_start and max_length

Code:

C++ Code

#include<bits/stdc++.h>
using namespace std;

void MaxLengthWords(string str, string &maxWord)
{
       int len = str.length();
       int i = 0, j = 0;


       int min_length = len, max_length = 0, max_start = 0;


       while (j <= len)
       {
              if (j < len && str[j] != ' ')
                     j++;

              else
              {
                     int curr_length = j - i;

                     if (curr_length > max_length)
                     {
                            max_length = curr_length;
                            max_start = i;
                     }
                     j++;
                     i = j;
              }
       }

       maxWord = str.substr(max_start, max_length);
}

// Driver code
int main()
{
       string str = "Google Docs";
       string maxWord;
       MaxLengthWords(str, maxWord);


       cout << "Largest Word is: " << maxWord << endl;
}

Output: Largest Word is: Google

Time Complexity: O(n) + O(n) = O(n)

Reason – O(n) for traversal , O(n) for using substr function

Space Complexity: O(n)

Reason – Using a string to print answer

Java Code

import java.util.*;
public class Solution {
       static String maxLength(String str) {
              int len = str.length();
              int i = 0, j = 0;
              String maxWord="";
              int max_length = 0, max_start = 0;

              while (j <= len) {
                     if (j < len && str.charAt(j) != ' ')
                            j++;

                     else {
                            int curr_length = j - i;

                            if (curr_length > max_length) {
                                   max_length = curr_length;
                                   max_start = i;
                            }
                            j++;
                            i = j;
                     }
              }

              maxWord = str.substring(max_start, max_length);
              return maxWord;
       }

       public static void main(String[] args) {
              String str = "Google Docs";

              System.out.print("Largest Word is: "+maxLength(str));
             

       }
}

Output: Largest Word is: Google

Time Complexity: O(n) + O(n) = O(n)

Reason – O(n) for traversal , O(n) for using substr function

Space Complexity: O(n)

Reason – Using a string to print answer

Special thanks to Shreyas Vishwakarma for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article