Problem

Submissions

Hints & solutions

Discuss

Occurrence Of Each Word

Easy

0/40

Average time to solve is 10m

Contributed by

15 upvotes

Asked in companies

Problem statement

You are given a string S of words. Your task is to count the occurrence of each word present in the string S. A word is a sequence of one or more non-space characters, and there can be multiple spaces between two words, and also there can be leading or trailing spaces in a string S.

For Example:

For the given string  “what we think we become”

“what”,” think”, and “become” occurs 1 time, and “we” occurs 2 times in the given string.

Detailed explanation ( Input/output format, Notes, Images )

Input format :

The first and the only line of input contains a string S.

Output format :

For each unique word in the given string, print the word along with its count of occurrence separated by a space in the new line.

Note:

You can print the output in any order.

Constraints :

0 <= |S| <= 10^5 

Time Limit: 1sec

Sample Input 1 :

learning to learn

Sample Output 1 :

learn 1
learning 1
to 1

Explanation For Sample Input 1:

For the given string, “learning”, “to”, and “learn” occurs only 1 time.

Sample Input 2 :

what we think we become

Sample Output 2 :

think 1
what 1
we 2
become 1

Hint 1

Hint 2

Think of brute force by checking for each unique word and count its occurrence in the rest of the string.

Approaches (2)

Approach 1

Approach 2

Brute Force

Steps:

We iterate a given string, and while iterating the string, we maintain a temporary string word that stores the current word and then checks if we already count the word's occurrence previously by checking whether the word is present in the visited list.
If the word is not present, then insert it in the visited list, and count the occurrences of the word in the rest of the string.
Else, we simply skip that iteration.

Time Complexity

O(N * (M+N)), where N is the length, and M is the number of unique words in the given string.

In the worst case, for each word in the string (O(N)), we will check if a current word is present in the visited list that takes O(M), and count the occurrence of a current word in the rest of the string (O(N)).

Hence the overall complexity will be O(N * (M+N) time.

Space Complexity

O(M), where M is the number of unique words in the given string.

In the worst case, we will be storing all unique words present in the string in the visited list.

(100% EXP penalty)

Occurrence Of Each Word

Console