1. Description
You are given a sequence of logs containing two types of operations:
- switch group: changes the current group.
- push item: adds an item to the current group. Adding the same item to the same group multiple times only counts once.
Return the name of the group that contains the largest number of distinct items after processing all logs.
2. Solution
Hash Map with Hash Sets
n = logs.size()
Time complexity: O(n)
Space complexity: O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| // Maintain a set of distinct items for each group while processing the logs.
// After each insertion, update the group with the largest set.
string solution(const vector<string>& logs) {
unordered_map<string, unordered_set<string>> items;
string current_group, result;
for (const string& log : logs) {
if (log[0] == 's') {
current_group = log.substr(7);
} else {
string item = log.substr(5);
items[current_group].insert(item);
if (result.empty() ||
items[current_group].size() > items[result].size()) {
result = current_group;
}
}
}
return result;
}
|