Registration System
A new e-mail service needs a registration system. Users send \(n\) requests, one after another, and each request contains a name.
- If the name is not yet in the database, the system inserts it and responds
OK. - If the name is already in the database, the system forms a new name by appending the smallest number \(i \ge 1\) such that
name\(i\) is not yet in the database (name1,name2, …). It inserts the new name into the database and responds with it.
Constraints:
- \(1 \le n \le 10^5\)
- Each name is non-empty, has at most \(32\) characters, and contains only lowercase Latin letters.
Input:
- First line: integer \(n\) — the number of requests.
- Next \(n\) lines: one name per line.
Output:
- \(n\) lines — the response of the system to each request.
Example:
Input:
6
first
first
second
second
third
third
Output:
OK
first1
OK
second1
OK
third1
Solution
We keep a map<string, int> that stores, for each name, how many times it has been requested so far.
- If the count of the name is \(0\), the name is new, and we print
OK. - If the count is \(c > 0\), the names
name,name1, …,name\((c-1)\) are already taken, so we printname\(c\).
In both cases we then increase the count of the name by \(1\).
This is correct because every requested name contains only letters. A generated name such as first1 contains a digit, so nobody can request it, and the only way it enters the database is through the counter of first.
For a name that is not yet in the map, count[name] creates it with value \(0\). The function to_string converts a number to a string, and + joins two strings.
Each request makes \(O(\log n)\) map operations, so the whole solution takes \(O(n \log n)\) time (ignoring the length of the names).
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {
int n;
cin >> n;
// name -> how many times this name was requested before
map<string, int> count;
for (int i = 0; i < n; i++) {
string name;
cin >> name;
if (count[name] == 0) {
cout << "OK\n";
} else {
cout << name + to_string(count[name]) << "\n";
}
count[name]++;
}
}