Occurrence Of Each Word
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.

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

Question

Occurrence Of Each Word

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.

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

Accepted Answer

In this program will take a string and a character as an input. And it will count the occurrence of a given character. This program also count spaces.

Accepted Answer

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.

Space Complexity: OtherExplanation:

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.

Time Complexity: OtherExplanation:

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.

Accepted Answer

Using Map

A better solution is to use a Map that stores a unique word as a key and count its occurrence in a given string as a value.

Steps:

We iterate a given string and check whether the current word is already present in a map or not. If the current word is present, then increment the value of the current word in a map otherwise insert the current word as a key and 1 as a value in a map.
Then we iterate over the keys in the map and print the key-value pair as the output.

Space Complexity: OtherExplanation:

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 map.

Time Complexity: OtherExplanation:

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

In the worst case, we will be traversing the whole string O(N), and traversing the Map takes O(M). Hence the overall complexity will be O(N+M).

Top Virtusa Consulting Services Associate Software Engineer interview questions & answers

Popular interview questions of Associate Software Engineer

Top HR questions asked in Virtusa Consulting Services Associate Software Engineer