Elliot and His Website

Moderate
0/80
profile
Contributed by
6 upvotes
Asked in companies
AmazonMindInventoryGoogle inc

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”}.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
3
ab
ab
ab
2
xy
xy1
Sample Output 1 :
ab
ab0
ab1
xy
xy1
Explanation For Sample Output 1 :
For the first test case, since “ab” is not present in the database for the first time, it will be given the username “ab”, for the second and the third time “ab” is already present in the array, hence they will be given the username “ab0” and “ab1”, respectively.

For the second test case, both “xy” and “xy1” are not present in the database, hence they will be given the username “xy” and “xy1”.
Sample Input 2 :
2
3
ninjas
ninjas1
ninjas
5
mrrobot
mrobot
mobot
mrrobo
mrrob
Sample Output 2 :
ninjas
ninjas1
ninjas0
mrrobot
mrobot
mobot
mrrobo
mrrob
Hint

Iterate through all the strings and check if the current string is present in the database or not.

Approaches (2)
Naive 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”.
Time Complexity

O( |S| * N ^ 3), where |S| is the maximum length of the strings and N is the total number of strings.


Since we are iterating through the whole string and using a while loop till we found a suitable match, the total time complexity of this approach will be O( |S| * N ^ 3).

Space Complexity

O( |S| * N ), where |S| is the maximum length of the strings and N is the total number of strings.

 

Since we are using an ArrayList “database” to store all the usernames. 

Hence the space complexity will be O( |S| * N ).

Code Solution
(100% EXP penalty)
Elliot and His Website
Full screen
Console