Find most repeated word in a string Java hackerrank solution

C++Server Side ProgrammingProgramming

Inhaltsverzeichnis Show

Solution Approach
Optimized Approach 2:

In this problem, we are a string str consisting of comma separated words. Our task is to find the first repeated word in a string.

We need to find the first word 'string between two spaces' which gets repeated in the string.

Let's take an example to understand the problem,

Input : str = "C program are easy to program" Output : program

Solution Approach

A simple solution to the problem is using hashmap data structure. To find the first repeated word, we will store each word and its count (number of times it appeared in the string ) in the hashmap. For this we will keep checking if the current word is present or not.

Then we will print the first work with more than one occurrence count in the hashmap.

Example

Program to illustrate the working of our solution

#include <bits/stdc++.h> using namespace std; string findFirstRepeatWord(string str){ istringstream iss(str); string word; unordered_map<string, int> wordCountMap; while (getline(iss, word, ' ')) { if (wordCountMap.find(word) != wordCountMap.end()) wordCountMap[word] ++; else wordCountMap.insert(make_pair(word, 1)); } istringstream iss2(str); while (getline(iss2, word, ' ')) { int count = wordCountMap[word]; if (count > 1) { return word; } } return "NoRepetition"; } int main(){ string str = "C program are easy to program"; string repeatedWord = findFirstRepeatWord(str); if (repeatedWord != "NoRepetition") cout<<"The first repeated word is '"<<repeatedWord<<"'"; else cout<<"No word is Repeated in the string"; return 0; }

Output

The first repeated word is 'program'

This program uses a lot of in-build functions for making the task easier.

Updated on 27-Jan-2022 10:50:35

Map and Map.Entry interface will be used as the Map interface maps unique keys to values. A key is an object that is used to retrieve a value at a later date. The Map.Entry interface enables you to work with a map entry. Also, we will use the HashMap class to store items in “key/value” pairs and access them by an index of another type.

Illustration:

Suppose the content of the sample text file is as follows:

Input: A text file containing sequence of arbitrary words

“How to count the number of occurrence of each word? How to count number or each word in string. Calculating frequency of each word in a sentence in java.”

Output: List of words that have the maximum occurrence
in = 3 each = 3 of = 3 to = 3

Implementation: Sample file input image is as follows:

Example

 
import java.io.FileNotFoundException;

import java.util.HashMap;

import java.util.Map.Entry;

import java.util.Scanner;

    static void getWords(String fileName,

                         Map<String, Integer> words)

        throws FileNotFoundException

        Scanner file = new Scanner(new File(fileName));

            String word = file.next();

            Integer count = words.get(word);

    static int getMaxOccurrence(Map<String, Integer> words)

        for (Entry<String, Integer> word :

            if (word.getValue() > max) {

    public static void main(String[] args)

        throws FileNotFoundException

        Map<String, Integer> words

            = new HashMap<String, Integer>();

        getWords("C:\\Users\\dell\\sample.txt", words);

        int max = getMaxOccurrence(words);

        for (Entry<String, Integer> word :

            if (word.getValue() == max) {

                System.out.println(word);

Output:

Given a string, Find the 1st repeated word in a string

Examples:

Input : "Ravi had been saying that he had been there" Output : had Input : "Ravi had been saying that" Output : No Repetition Input : "he had had he" Output : he

question source : https://www.geeksforgeeks.org/goldman-sachs-interview-experience-set-29-internship/amp/

Simple Approach : Start iterating from back and for every new word , store it in unordered map . For every word which has occurred more than one , update ans to be that word , at last reverse ans and print it.

Implementation:

unordered_map<string,int> mp;

for(int i=s.length()-1;i>=0;i--)

reverse(ans.begin(),ans.end());

string u="Ravi had been saying that he had been there";

string v="Ravi had been saying that";

string w="he had had he";

 
  public static void solve(String s)

    HashMap<String, Integer> mp

    for (int i = s.length() - 1; i >= 0; i--) {

      if (s.charAt(i) != ' ') {

        if (!mp.containsKey(t)) {

          mp.put(t, mp.get(t) + 1);

    if (!mp.containsKey(t)) {

      mp.put(t, mp.get(t) + 1);

      StringBuilder input1 = new StringBuilder();

      System.out.println(input1);

      System.out.print("No Repetition\n");

  public static void main(String[] args)

      = "Ravi had been saying that he had been there";

    String v = "Ravi had been saying that";

    String w = "he had had he";

for i in range(len(s) - 1,-1,-1):

u = "Ravi had been saying that he had been there"

v = "Ravi had been saying that"

 
using System.Collections.Generic;

  static void solve(string s)

    Dictionary<string, int> mp = new Dictionary<

    for (int i = s.Length - 1; i >= 0; i--) {

      char[] charArray = ans.ToCharArray();

      Array.Reverse(charArray);

      Console.WriteLine(new string(charArray));

      Console.Write("No Repetition\n");

  public static void Main()

      = "Ravi had been saying that he had been there";

    string v = "Ravi had been saying that";

    string w = "he had had he";

for(let i = s.length - 1; i >= 0; i--)

ans = [...ans].reverse().join("");

document.write("No Repetition");

const u = "Ravi had been saying that he had been there";

const v = "Ravi had been saying that";

const w = "he had had he";

Output had No Repetition he

Another Approach: The idea is to tokenize the string and store each word and its count in hashmap. Then traverse the string again and for each word of string, check its count in created hashmap.

Implementation:

 
string findFirstRepeated(string s)

    unordered_map<string, int> setOfWords;

    while (getline(iss, token, ' ')) {

        if (setOfWords.find(token) != setOfWords.end())            

            setOfWords.insert(make_pair(token, 1));       

    while (getline(iss2, token, ' ')) {

        int count = setOfWords[token];

    string s("Ravi had been saying that he had been there");

    string firstWord = findFirstRepeated(s);

    if (firstWord != "NoRepetition")

        cout << "First repeated word :: "

        cout << "No Repetitionn";

 
    static String findFirstRepeated(String s)

        String token[] = s.split(" ");

        HashMap<String, Integer> setOfWords = new HashMap<String, Integer>();

        for (int i=0; i<token.length; i++) {

            if (setOfWords.containsKey(token[i]))           

                setOfWords.put(token[i], setOfWords.get(token[i]) + 1);

                setOfWords.put(token[i], 1);   

        for (int i=0; i<token.length; i++) {

            int count = setOfWords.get(token[i]);

    public static void main(String args[])

        String s = "Ravi had been saying that he had been there";

        String firstWord = findFirstRepeated(s);

        if (!firstWord.equals("NoRepetition"))

            System.out.println("First repeated word :: " + firstWord);

            System.out.println("No Repetitionn");

static findFirstRepeated(s)

var token = s.split(" ");

var setOfWords = new Map();

for (let i=0; i < token.length; i++)

if (setOfWords.has(token[i]))

setOfWords.set(token[i],setOfWords.get(token[i]) + 1);

setOfWords.set(token[i],1);

for (let i=0; i < token.length; i++)

var count = setOfWords.get(token[i]);

var s = "Ravi had been saying that he had been there";

var firstWord = GFG.findFirstRepeated(s);

if (firstWord !== "NoRepetition")

console.log("First repeated word :: " + firstWord);

console.log("No Repetitionn");

Output First repeated word :: had

As all the words in a sentence are separated by spaces.
We have to split the sentence by spaces using split().
We split all the words by spaces and store them in a list.
Use Counter function to count frequency of words
Traverse the list and check if any word has frequency greater than 1
If it is present then print the word and break the loop

Implementation::

from collections import Counter

def firstRepeatedWord(sentence):

lis = list(sentence.split(" "))

sentence = "Vikram had been saying that he had been there"

print(firstRepeatedWord(sentence))

Instead of tracking the counts for a specific token(word), we can keep track of the first occurrence of the token(word) using an unordered map. This would not require any extra loop to traverse in a hashmap or a string to find the repeated string. Thus, it eventually transforms the time complexity from O(2*n) to O(n) while the space complexity remains the same.

Implementation:

unordered_map<string, int>

if (s[j] == ' ' || j == n) {

cout << "No Repetition" << endl;

= "Ravi had been saying that he had been there";

string s2 = "Ravi had been saying that";

string s3 = "he had had he";

Output had No Repetition he

Instead of counting a number of occurrences of each word which will have O(N) time and space complexity, where N is number of words, we can stop when the count of any word becomes 2. That is no need to iterate through all the words in string.

Let’s say our first repeated word is present at Mth index, then

By using this approach, space and time complexity reduced from O(N) to O(M).

Where,

N: number of words in a string.

M: Index at which first repeating word is present

However, Worst case( When no word is being repeated or the word being repeated is present at last) time and space complexity will still be O(N).

Steps:

Create a default dictionary with an initial value of 0, to keep track count of words.
Iterate through each word in a sentence and increment the count of that word by 1.
If (count of the word) > 1, return the word.
If the count of none of the words is greater than 1 then that is we are outside our loop then return “No word is being repeated”.

Implementation:

from collections import defaultdict

def first_repeating_word(s):

word_count = defaultdict(lambda: 0)

return 'No word is being repeated'

if __name__ == '__main__':

s = "Ravi had been saying that he had been there"

print(first_repeating_word(s))

function first_repeating_word(s){

let word_count = new Map()

for(let i of s.split(' ')){

word_count.set(i,word_count.get(i) + 1);

else word_count.set(i,1);

if(word_count.get(i) > 1)

return 'No word is being repeated'

let s = "Ravi had been saying that he had been there"

document.write(first_repeating_word(s))

Time complexity: O(M)
Space Complexity: O(M)

Optimized Approach 2:

Instead of counting a number of occurrences of each word which will have O(N) time and space complexity, where N is a number of words, we can just store words in a HashSet, and as soon as we reach a word that is already present in the HashSet we can return.

Implementation:

 
string findFirstRepeated(string s)

    while (getline(iss, token, ' ')) {

        if (setOfWords.find(token) != setOfWords.end()) {

        setOfWords.insert(token);

    string s("Ravi had been saying that he had been there");

    string firstWord = findFirstRepeated(s);

    if (firstWord != "NoRepetition")

        cout << "First repeated word :: " << firstWord

        cout << "No Repetitionn";

 
    static String findFirstRepeated(String s)

        String token[] = s.split(" ");

        HashSet<String> set = new HashSet<String>();

        for(int i=0; i<token.length; i++){

            if(set.contains(token[i])){

    public static void main(String args[])

        String s = "Ravi had been saying that he had been there";

        String firstWord = findFirstRepeated(s);

        if (!firstWord.equals("NoRepetition"))

            System.out.println("First repeated word :: " + firstWord);

            System.out.println("No Repetitionn");

 
    static findFirstRepeated(s)

        var token = s.split(" ");

        for (let i=0; i < token.length; i++)

        var s = "Ravi had been saying that he had been there";

        var firstWord = GFG.findFirstRepeated(s);

        if (firstWord !== "NoRepetition")

            console.log("First repeated word :: " + firstWord);

        console.log("No Repetitionn");
# This code is contributed by mukulsomukesh

Output First repeated word :: had

This article is contributed by Aarti_Rathi and Mandeep Singh. If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to . See your article appearing on the GeeksforGeeks main page and help other Geeks.

Article Tags :