-
Notifications
You must be signed in to change notification settings - Fork 506
/
Copy pathSecond most repeated string in a sequence.cpp
45 lines (37 loc) · 1.17 KB
/
Second most repeated string in a sequence.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/*
Second most repeated string in a sequence
==========================================
Given a sequence of strings, the task is to find out the second most repeated (or frequent) string in the given sequence.
Note: No two strings are the second most repeated, there will be always a single string.
Example 1:
Input:
N = 6
arr[] = {aaa, bbb, ccc, bbb, aaa, aaa}
Output: bbb
Explanation: "bbb" is the second most
occurring string with frequency 2.
Example 2:
Input:
N = 6
arr[] = {geek, for, geek, for, geek, aaa}
Output: for
Explanation: "for" is the second most
occurring string with frequency 2.
Your Task:
You don't need to read input or print anything. Your task is to complete the function secFrequent() which takes the string array arr[] and its size N as inputs and returns the second most frequent string in the array.
Expected Time Complexity: O(N*max(|Si|).
Expected Auxiliary Space: O(N*max(|Si|).
Constraints:
1<=N<=103
*/
string secFrequent(string arr[], int n)
{
priority_queue<pair<int, string>> pq;
unordered_map<string, int> m;
for (int i = 0; i < n; ++i)
m[arr[i]]++;
for (auto &i : m)
pq.push({i.second, i.first});
pq.pop();
return pq.top().second;
}