Find the Largest Word in a String

86.8k
0

Given a string, the task is to find the largest word present in the string.

A string can contain many words separated by spaces.

Example 1

Input:

s = "I love programming"

Output:

programming

Explanation:

The words are "I", "love", and "programming".

The word "programming" has the maximum length.

So, the largest word is "programming".

Example 2

Input:

s = "DSA is very important"

Output:

important

Explanation:

The words are "DSA", "is", "very", and "important".

The longest word is "important".

So, the output is "important".

Brute : Split the String into Words

The simplest approach is to split the sentence into individual words and examine them one by one. Similar to a teacher checking the height of students in a line and keeping track of the tallest student seen so far, we keep track of the longest word encountered while traversing the sentence. For each word, we compare its length with the length of the current longest word. If the current word is longer, we update our answer. By the end of the traversal, the stored word will be the longest word in the sentence, since every word has been checked exactly once.


Algorithm

  1. Split the string into words using space as the separator because we need to compare complete words, not individual characters.

  2. Create an empty string called largestWord because we need a place to store the longest word found so far.

  3. Traverse all words one by one because any word in the string can be the largest word.

  4. Compare the length of the current word with the length of largestWord because this tells us whether the current word is longer than the best answer found so far.

  5. If the current word is longer, update largestWord because we have found a better answer.

After checking all words, return largestWord because it stores the largest word in the string.

Dry Run

Split the String into Words

Split the String into Words

Solution

// C++ program to implement Find the Largest Word in a String
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Finds the longest word present in the given string.
// If multiple words have the same maximum length, the first one is returned.
string findLargestWord(string s) {
string largestWord = "";
string word;
// stringstream automatically separates words by spaces.
stringstream ss(s);
while (ss >> word) {
// Update only when a strictly longer word is found.
if (word.length() > largestWord.length()) {
largestWord = word;
}
}
return largestWord;
}
};
int main() {
string s = "I love programming";
Solution obj;
cout << obj.findLargestWord(s);
return 0;
}

Time Complexity:
The algorithm traverses the string to separate it into individual words and then checks each word as required. Since every character in the string is processed only once during these operations, the total running time is proportional to the length of the string. Therefore, the time complexity is O(N), where N is the length of the string.

Space Complexity:
The algorithm stores the extracted words in an array or list after splitting the string. In the worst case, the storage required for these words can be proportional to the size of the input string. Therefore, the space complexity is O(N).

Optimal: Single Traversal Without Splitting


The previous method is simple, but it requires storing all the words separately after splitting the string. We can optimize this by traversing the string character by character and constructing each word manually as we read it. This avoids the need to store all words at once. Whenever we encounter a space, it indicates that the current word has ended, so we compare its length with the longest word found so far and update the answer if necessary. After that, we clear the current word and start building the next one. At the end of the traversal, we perform one final comparison for the last word, since a word may end when the string itself ends. This approach works because every word is processed exactly once, either when a space is encountered or when the string reaches its end.


Algorithm

  • Create an empty string called largestWord because it stores the longest word found so far.

  • Create another empty string called currentWord because it stores the word we are currently reading.

  • Traverse the string character by character because we need to find where each word starts and ends.

  • If the current character is not a space, add it to currentWord because it means we are still reading the same word.

  • If the current character is a space, it means the current word has ended.

  • Compare currentWord with largestWord because we need to check whether the current word is longer than the longest word found so far.

  • If currentWord is longer, update largestWord because we have found a better answer.

  • Clear currentWord because the next word should be stored fresh from the beginning.

  • After the loop ends, compare currentWord one last time because the last word may not end with a space.

Return largestWord because it stores the largest word in the string.

Dry Run

Single Traversal Without Splitting

Single Traversal Without Splitting


Solution

// C++ program to implement Find the Largest Word in a String
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Finds the longest word in the string without using built-in split.
// If two words have the same maximum length, the first one is returned.
string findLargestWord(string s) {
string largestWord = "";
string currentWord = "";
for (char ch : s) {
if (ch != ' ') {
currentWord += ch;
} else {
// A space means the current word is complete, so we compare it with the largest word.
if (currentWord.length() > largestWord.length()) {
largestWord = currentWord;
}
// Clear currentWord to start building the next word.
currentWord = "";
}
}
// The last word must be checked separately because the string may not end with a space.
if (currentWord.length() > largestWord.length()) {
largestWord = currentWord;
}
return largestWord;
}
};
int main() {
string s = "I love programming";
Solution obj;
cout << obj.findLargestWord(s);
return 0;
}

  • Time Complexity:
    The algorithm traverses the string to separate it into individual words and then checks each word as required. Since every character in the string is processed only once during these operations, the total running time is proportional to the length of the string. Therefore, the time complexity is O(N), where N is the length of the string.

  • Space Complexity:
    The algorithm stores the extracted words in an array or list after splitting the string. In the worst case, the storage required for these words can be proportional to the size of the input string. Therefore, the space complexity is O(N).

FAQs about Find the Largest Word in a String

1. What does largest word mean?

Largest word means the word with the maximum number of characters.

2. What should we return if two words have the same length?

Usually, we return the first word with the maximum length.

3. Can we solve this without splitting the string?

Yes. We can traverse the string character by character and build each word manually.

4. Why do we need to check the last word after the loop?

Because the last word may not be followed by a space. So, it may not get checked inside the loop.

5. What if the string has only one word?

Then that word itself is the largest word.








String

Read Similar Blogs

TrieArraysData StructuresHashingStringSorting

Design Add and Search Words Data Structure

Design a data structure that supports adding words and searching words later. The search word may contain lowercase letters and the dot character . . The dot . can match any one lowercase English l...

50.7k
StringRecursionArrays

Introduction to String Advanced

1. Basic Pattern Matching Problem Suppose a word needs to be searched inside a larger sentence or string. The goal is to find all starting positions where the smaller pattern exactly...

66.8k
String

Introduction to Prefix-Suffix in String

Input: s = "ababab" Output: 4 Explanation: The prefix "abab" and the suffix "abab" are the same, so the longest prefix-suffix length is 4 . Input: s = "aabcdaabc" Output: 4 Explanation: The string...

81.6k
Comments0