Second Most Repeated Word in a Sequence in Java
The task is to identify the second most repeated (or frequent) string in a given series of strings. There will be only one word or string in the sequence that is the second most repeated; that is, no two words or strings will be the second most repeated.
Example 1:
Input:
{"aab", "aab", "pqr", "zxy", "pqr", "aab"}
Output:
The second most repeated word in the given sequence is pqr.
Explanation:
In the given series of words, "aab" is repeated three times, and "pqr" is repeated two times, which is the second most repeated one. Hence, the output is "pqr".
Example 2:
Input:
{"aaa", "cbc", "tae", "aaa", "jtp", "tae","cbc"}
Output:
The second most repeated word in the given sequence is jtp.
Explanation:
In the given series of words, "aaa" is repeated two times, and similarly, the words "cbc" and "tae" are repeated two times. The word "jtp" is repeated only once in the given sequence and which is second most repeated one. Hence, the output is "jtp".
Approach: Brute Force Method
Three independent steps are carried out over the sequence in this brute force method: one to count occurrences, one to identify the maximum and second maximum occurrences, and one to identify the word with the second maximum occurrence. Although this method is less effective than the previous HashMap-based method, the intended outcome still needs to be reached.
Implementation:
FileName: BruteForceSecondRepeated.java
import java.io.*;
import java.util.*;
public class BruteForceSecondRepeated
{
public static String SecondWordFrequence(String array[], int n)
{
// Creation of the Hashmap to store the words as keys and occurences as values
HashMap<String, Integer> map = new HashMap<>();
// counts the occurences of the words in the sequences present in an array list
for (int i = 0; i < n; i++)
{
if (map.containsKey(array[i]))
{
map.put(array[i], map.get(array[i]) + 1);
}
else
{
map.put(array[i], 1);
}
}
// finds the word that has occured the maximum number of times
int max = Collections.max(map.values());
// A list called ArrayList 'ar' is made to hold the occurrence counts that come in low of the maximum.
ArrayList<Integer> ar = new ArrayList<>();
for (Map.Entry<String, Integer> j : map.entrySet())
{
if (j.getValue() != max)
{
ar.add(j.getValue());
}
}
// sorts the occurences count of the words
Collections.sort(ar);
// returns the second most repeated word int the sequence.
for (Map.Entry<String, Integer> x : map.entrySet())
{
if (x.getValue() == ar.get(ar.size() - 1))
{
return x.getKey();
}
}
return "-1";
}
public static void main(String[] args)
{
String array[] = {"aaa", "cbc", "tae", "aaa", "jtp", "tae","cbc"};
int n = array.length;
String result = SecondWordFrequence(array, n);
System.out.println("The second most repeated word in the given sequence is " + result);
}
}
Output:
The second most repeated word in the given sequence is jtp
Complexity Analysis:
The Time Complexity for the above approach by using Brute-force is O(NLog(N)), and the Space Complexity is O(N).
Approach: Reducing the Time Complexity
In order to identify the second most repeated word in a sequence, we will first use a hash table to store the frequency of each string. Next, we will iterate through the hash table. Declare a hash table initially with name occurrence. We will now save the frequency of each text that is placed in the vector known as a sequence using the stated hash table. Currently, the function SecondMostRepeatedWord iterates through the hash table until the second most repeated string is located. Print the string.
Implementation:
FileName: FindSecondRepeatedWord.java
import java.io.*;
import java.util.*;
public class FindSecondRepeatedWord
{
static String SecondMostRepeatedWord(Vector<String> sequen)
{
// Keep a record of every term and its occurrence.
HashMap<String, Integer> occur = new HashMap<String,Integer>(sequen.size())
{
@Override
public Integer get(Object keyval)
{
return containsKey(keyval) ? super.get(keyval) : 0;
}
};
for (int i = 0; i < sequen.size(); i++)
occur.put(sequen.get(i), occur.get(sequen.get(i))+1);
// find the second most frequent occurrence
int first_maxval = Integer.MIN_VALUE, sec_maxval = Integer.MIN_VALUE;
Iterator<Map.Entry<String, Integer>> iterate = occur.entrySet().iterator();
while (iterate.hasNext())
{
Map.Entry<String, Integer> entry = iterate.next();
int value = entry.getValue();
if( value > first_maxval)
{
sec_maxval = first_maxval;
first_maxval = value;
}
else if (value > sec_maxval && value != first_maxval)
sec_maxval = value;
}
// Return a string to sec_max whose occurrence equals
iterate = occur.entrySet().iterator();
while (iterate.hasNext())
{
Map.Entry<String, Integer> entry = iterate.next();
int value = entry.getValue();
if (value == sec_maxval)
return entry.getKey();
}
return null;
}
public static void main(String[] args)
{
String array[] = {"aaa", "cbc", "tae", "aaa", "jtp", "tae","cbc"};
List<String> sequen = Arrays.asList(array);
System.out.println("The second most repeated word in the given sequence is " + SecondMostRepeatedWord(new Vector<>(sequen)));
}
}
Output:
The second most repeated word in the given sequence is jtp
Complexity Analysis:
The Time Complexity by using the above approach is O(N) and the Space Complexity is O(N), where N denotes the specific size of the given vector.