Second Most Repeated Word
You are given an array of strings ‘ARR’. You have to find out the second most repeated word in the array ‘ARR’. It is guaranteed every string occurs a unique number of times in the array. If there is only one unique string in the array, return an empty string.

Example:-

N = 5 S = [‘aaa’, ‘bbb’, ‘ccc’, ‘aaa’, ‘bbb’, ‘aaa’] ANSWER:- The answer should be ‘bbb’ as it is repeated 2 times and is the second most repeated word in the array [after the word ‘aaa’ which is repeated 3 times].

Input Format :

The first line contains a single integer ‘T’ representing the number of test cases. Then each test case follows. The first line of every test case contains an integer ‘N’ denoting the length of the array. The next line of every test case contains ‘N’ strings denoting the string in the array.

Output Format :

For each test case, return the second most repeated character in the array. If there is only one unique string in the array, return an empty string. The output of each test case should be printed in a separate line.

Note :

You are not required to print anything, it has already been taken care of. Just implement the function.

Constraints :

1

Question

Second Most Repeated Word

You are given an array of strings ‘ARR’. You have to find out the second most repeated word in the array ‘ARR’. It is guaranteed every string occurs a unique number of times in the array. If there is only one unique string in the array, return an empty string.

Example:-

N = 5
S = [‘aaa’, ‘bbb’, ‘ccc’, ‘aaa’, ‘bbb’, ‘aaa’]

ANSWER:- The answer should be ‘bbb’ as it is repeated 2 times and is the second most repeated word in the array [after the word ‘aaa’ which is repeated 3 times].

Input Format :

The first line contains a single integer ‘T’ representing the number of test cases. Then each test case follows.

The first line of every test case contains an integer ‘N’ denoting the length of the array.

The next line of every test case contains ‘N’ strings denoting the string in the array.

Output Format :

For each test case, return the second most repeated character in the array. If there is only one unique string in the array, return an empty string.

The output of each test case should be printed in a separate line.

Note :

You are not required to print anything, it has already been taken care of. Just implement the function.

Constraints :

1 <= T <= 10
1 <= N <= 1000
1 <= |ARR[i]| <= 1000

Note:- It is guaranteed that every string has a unique frequency in the array.

Time Limit = 1 sec

Accepted Answer

Hashing

Iterate through the array and store the frequency of each string in the array. Find out the maximum frequency word which occurs in the array and print the word which has the maximum frequency but has less frequency than the maximum one.

Algorithm:-

Initialize an empty string named ANS to store the final answer.
Initialize a dictionary named FREQ to store the frequency of the words in the array.
Iterate through the array from 0 to N.(Let’s say the iterator is i).
1. Increment FREQ[ARR[i]] by 1.
Initialize a variable named MAX_FREQ with the maximum value of the dictionary FREQ.
Initialize a variable named SEC_MAX with 0.
Iterate through the dictionary FREQ.(Let’s say the iterator is i).
1. If FREQ[i] is greater than SEC_MAX and but less than MAX_FREQ,
  1. Update SEC_MAX to FREQ[i] and ANS to i.
Return ANS.

Space Complexity: OtherExplanation:

O(N*max(|ARR[i]|), where N is the length of the array ARR.

We are iterating through the array once and storing every string in the dictionary, so the space complexity is O(N*max(|ARR[i]|).

Time Complexity: OtherExplanation:

O(N*max(|ARR[i]|), where N is the length of the array ARR.

We are iterating through the array once and storing every string in the dictionary which takes |ARR[i]| time each, so the time complexity is O(N*max(|ARR[i]|).

Java (SE 1.8)

/*

    Time Complexity: O(N*max(|ARR[i]|)

    Space Complexity: O(N*max(|ARR[i]|)



    where 'N' is the length of input array ARR

*/



import java.util.*;

public class Solution {



    public static String second_repeat(String[] arr, int n) {

        

        // Create a default dictionary to store the count of each element

        HashMap count = new HashMap<>();

        int ma = 0;

        for(int i = 0; i < n; i++){

            if(count.containsKey(arr[i])){

                count.put(arr[i],count.get(arr[i]) + 1);

            }

            else{

                count.put(arr[i], 1);

            }

            

            ma = Math.max(ma, count.get(arr[i]));

        }

        

        int sec_max = 0;

        String ans = "";

        

        // Iterate over the dictionary and find the element which occurs

        // the second most number of times.

        for (Map.Entry i: count.entrySet()){

            if (i.getValue() > sec_max && i.getValue() < ma){

                sec_max = i.getValue();

                ans = i.getKey();

            }

        }

        return ans;

    }

}

Python (3.5)

'''

    Time Complexity: O(N * max(|ARR[i]|))

    Space Complexity: O(N * max(|ARR[i]|))



    where 'N' is the number of the strings.

'''



from collections import defaultdict





def second_repeat(arr, n):



    # Create a default dictionary to store the count of each element

    count = defaultdict(int)

    for i in range(n):

        count[arr[i]] += 1

        

    ma = max(count.values())

    sec_max = 0

    ans = ""

    

    # Iterate over the dictionary and find the element which occurs

    # the second most number of times.

    for i in count:

        if count[i] > sec_max and count[i] < ma:

            sec_max = count[i]

            ans = i

    return ans

C++ (g++ 5.4)

/*
    Time Complexity: O(N*max(|ARR[i]|)
    Space Complexity: O(N*max(|ARR[i]|)

    where 'N' is the length of input array ARR
*/


#include
string second_repeat(vector &arr, int n){

    
    // Create a default dictionary to store the count of each element
    map count;
    int ma = 0;
    for(int i = 0; i < n; i++){
        count[arr[i]] += 1;
        ma = max(ma, count[arr[i]]);
    }
    
    int sec_max = 0;
    string ans = "";
    
    // Iterate over the dictionary and find the element which occurs
    // the second most number of times.
    for (pair i : count){
        
        if (i.second > sec_max and i.second < ma){
            sec_max = i.second;
            ans = i.first;
        }
    }
    return ans;
}