Last Updated: 29 Aug, 2021

Elliot and His Website

Moderate

Asked in companies

Solve now

Problem statement

Elliot wants to build a website that will offer free hacking courses to anyone who registers. He wants to make sure that everyone who registers on his site must have a unique username. So if a user with a username ‘s’ is already registered with the system, his username will be concatenated with the smallest non-negative integer such that the new username is not present in the database.

Every time a string with the same username registers, the order of registration will be s, s0, s1, s2….. s9, s10, s11.

You are given ‘n’ usernames, for each username find the username which will be given to each user.

Note :

Initially, there are no usernames in the database.

For Example :

Let s = {“ninjas”, “ninja”, “ninjas”, “ninjas1”}

Now In this example, first and second users are not present in the database, so they will be given the same usernames i.e. “ninjas”, “ninja”, now for the third user, “ninjas” is already present in the database, so he will be given the username “ninjas0” and for the last username, “ninjas1” is also not present in the database so he will be given the same username.

Hence the final usernames in the database will be {“ninjas”, “ninja”, “ninjas0”, “ninjas1”}.

Input Format :

The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow.

The first line of each test case will be an integer ‘n’ denoting the number of users who want to register.

Next ‘n’ lines of the input will contain a string ‘s’ denoting the usernames.

Output Format :

For each test case, print ‘n’ strings denoting the usernames given by the website.

Output for each test case will 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 and return the answer.

Constraints :

1 <= T <= 10
1 <= n <= 5000
1 <= |S| <= 1000, where |S| represents the length of the String S.

Time limit: 1 sec

Solve now

Approaches

01 Approach

In this approach, we will start iterating through every username and check if the current username is present in the database or not. If the current username is not present in the database then we will push it to the vector database else we will add an integer to its end.

The steps are as follows:

Iterate through the list of strings s from 0 to n(say iterator be i):
- Initialize a variable “count” in which we will store the minimum index which can be added to the current string such that it can make the username unique.
- If the current element s[i] is not present in the list “database” add it to the list and continue.
- Else if the current element is already present in the “database” then take a while loop till we don’t find a unique username.
  - Concatenate “count” to the last of the current element and check if the username is present or not.
  - If the element is present then increase “count” and concatenate “count” to the string again to check.
  - Break the loop when you find a unique string.
Return “database”.

Solve now

02 Approach

In this approach, we will use the trie data structure to store all the usernames which have been assigned and will check for the uniqueness of the new username using this data structure.

The steps are as follows:

Create a struct/ class “trie” in which we will take some variables.
- Take an integer “lastIndex” in which we will store the last index which must be added to if more than one string ends on this node.
- Take a bool isLast to store whether or not any string ends on this point.
- A vector of “trie” named “next” of size 36 in which we will store all the next elements which are emerging from the current string, the first 26 indexes will store the 26 alphabets from a-z and the last 10 characters will store the integers from 0-9.
In the “main” function:
- Take a vector of string “answer” in which we will store the final strings.
- Take an Object/Struct of the trie “database”.
- Iterate through the vector of strings ‘s’ and call the “addInDatabase” function passing the current string, trie, and 0(to keep track of current index), If this function returns -1, that means s[i] is unique and has been added to the database. Else it will return a number that must be concatenated to the last of this string to make it unique.
- Push the string after concatenation(if needed) into the “answer” vector.
In the “addInDatabase” Function:
- Check if the current index is equal to s.length() return -1.
- Check if the current char in the string is null or not in the next of “database” trie:
  - if it is null, update “database” with not null and if the current index is the last index of the string then return -1.
  - Else call this function again with index = index + 1.
- Check if the current index is the last index of the string:
  - If the current index is the last element of the string and “database->next[position]” is not null then call the function “addInteger” to add an integer to the last of the string.
  - Return the “addInteger” function which will return the value which should be added to the last of the string.
  - Else if “database->next[position]” is null then update “isLast” = true and return -1.
- If the current index is not the last index return the “addIndatabase” function again with the next index.
In the “addInteger” function:
- Iterate from lastIndex of the current node of “database” till 100005(say iterator be i):
  - Return the minimum number which is not present in the “database” for that string.

Solve now