Count Words in a String Using String Traversal
Problem Statement
Write a program to count the number of words in a given string.
A word is a continuous group of characters separated by one or more spaces.
Example 1
Example 1
Input
s = "Hello World"Output
2
ExplanationThe string contains two words: "Hello" and "World".
Both words are separated by a single space.
So, the total number of words is 2.
Example 2
Example 2
Input
s = " I love DSA "Output
3Explanation
The string contains three words: "I", "love", and "DSA".
Extra spaces at the start, end, and between words should not be counted as words.
So, the total number of words is 3.
Brute : Using Split and Filtering
Intuition
The main goal is to separate the sentence into meaningful parts. In this problem, words are separated by spaces, so the first thought is to break the string wherever spaces appear.
But there is one small issue. If there are multiple spaces together, splitting the string can also create empty parts. These empty parts are not words, so they should be ignored.
This approach works because every real word is a continuous group of characters, and spaces only act as separators.
Algorithm
Split the string using space as the separator.
Create a counter to store the number of valid words.
Go through every part created after splitting.
If the part is not empty, count it as a word.
Return the final count.
Dry Run
Input
s = " I love DSA "
Diagram 1
Final Output
3
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: int countWords(string s) { // Create a string stream to read words from the string stringstream ss(s); // Store each word one by one string word; // Store the total number of words int count = 0; // Read words separated by spaces while (ss >> word) { // Increase count for every word found count++; } // Return the total number of words return count; }};int main() { // Store the input string string s = " I love DSA "; // Create object of Solution class Solution obj; // Print the number of words cout << obj.countWords(s); return 0;}Output: 3
Complexity Analysis
Time Complexity: O(N)
The string is scanned to split it into words, where N is the length of the string.
Space Complexity: O(W)
Extra space is used to store the words after splitting, where W is the number of words.
Optimal: Single Pass String Traversal
The previous approach is easy, but it creates an extra list or array of words. That is not always needed. The improvement is to count words while scanning the string, without storing all words separately.
Intuition
A word starts when a non-space character appears after a space or at the beginning of the string.
Think of reading a sentence written on paper. Spaces act like gaps between words. Whenever reading moves from a gap to an actual character, it means a new word has started.
So, instead of storing all words separately, the idea is to simply track whether the current position is inside a word or outside a word.
Whenever a new word starts, increase the count. This works because every word has exactly one starting point, and counting those starting points gives the total number of words.
Algorithm
Set the word count as
0.Set a flag to track whether the current position is inside a word.
Traverse the string from left to right.
If the current character is not a space and we are not inside a word, a new word has started.
Increase the count and mark that we are inside a word.
If the current character is a space, mark that we are outside a word.
Return the final count.
Dry Run
Input
s = " I love DSA "
Diagram 1
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: int countWords(string s) { // Store the total number of words int count = 0; // Track whether we are currently inside a word bool insideWord = false; // Traverse every character in the string for (char ch : s) { // If the current character is not a space and we are outside a word if (ch != ' ' && insideWord == false) { // A new word has started count++; // Mark that we are now inside a word insideWord = true; } // If the current character is a space else if (ch == ' ') { // Mark that we are outside a word insideWord = false; } } // Return the total number of words return count; }};int main() { // Store the input string string s = " I love DSA "; // Create object of Solution class Solution obj; // Print the number of words cout << obj.countWords(s); return 0;}Output: 3
Complexity Analysis
Time Complexity: O(N)
The string is traversed only once, where N is the length of the string.
Space Complexity: O(1)
Only a counter and a boolean flag are used. No extra word list is created.
Edge Cases
These are some important edge cases to consider:
If the string is empty, there are no characters and no words, so the answer should be
0.If the string contains only spaces, there is no continuous group of non-space characters, so the answer should be
0.If the string has spaces at the start or end, those spaces should not increase the word count.
If there are multiple spaces between two words, they should still act like a single separator.
If the string has only one word and no spaces, the answer should be
1.
FAQs about Count Words in a String
What is a word in this problem?
A word is a continuous group of characters separated by one or more spaces.
Should extra spaces be counted?
No. Spaces are only separators. They should not be counted as words.
What should be the answer for an empty string?
The answer should be 0 because there are no words.
Which approach is better?
The single-pass traversal approach is better because it does not store all words separately.
Can this problem be solved using split?
Yes. It is the easiest way, but it may use extra space to store the words.
Be the first to add a comment.